Suppose you are looking for a new apartment with a list of requirements such as a gym or school nearby. This algorithm will help you find an apartment that minimises the distance you would have to walk from your apartment to reach all of your required buildings.

The problem is as follows. You are given two inputs, a list of blocks where each block contains an apartment you could move into and a list of requirements. Note that the list of blocks may contain amenities that are not part of your requirements.

# list of blocks
blocks = [
            {"gym": False, "school": True, "clinic": False},
            {"gym": True, "school": False, "clinic": False},
            {"gym": True, "school": True, "clinic": False},
            {"gym": False, "school": True, "clinic": False},
            {"gym": False, "school": True, "clinic": True},
        ]

# list of requirements
requirements = ["gym", "school", "clinic"]
0           1            2             3            4
school                 school       school         school
           gym         gym                         
                                                   clinic

The output of the above would give the answer 3. At index 3, the gym and clinic are only 1 block away. The school is located on your block so no steps are needed. Any other index would not do better.

A brute force solution to the problem would be to iterate through the list of blocks. At the current iteration of the block, we then iterate through the list of requirements and at each requirement, we again iterate through the list of blocks to check if the requirements exist in the block. If it exists, we compare and update our minimum step for that requirement, which is instantiated as float(‘inf’).

def apartmentHunting(blocks, reqs):
    result = [float('-inf') for _ in range(len(blocks))]
    for currentIdx in range(len(blocks)):
        for req in reqs:
            step = float('inf')
            # compare from end to start
            for compareIdx in range(currentIdx - 1, -1, -1):
                if blocks[compareIdx][req]:
                    step = min(step, currentIdx - compareIdx)
            # compare from start to end
            for compareIdx in range(currentIdx, len(blocks)):
                if blocks[compareIdx][req]:
                    step = min(step, compareIdx - currentIdx)
            result[currentIdx] = max(result[currentIdx], step)
    return result.index(min(result))
  
  
0           1            2             3            4
school                 school       school         school
           gym         gym                         
                                                   clinic

For the above solution, we first instantiate an array of length equal to the length of blocks with float(‘-inf’) for every element. Consider our example input, starting at the first block and the first requirement which is gym, we check if the current block has gym. Block at index 0 has no gym, so we skip and move to the next block. Block at index 1 has gym, so we get the number of steps by calculating the difference of the compareIdx and the currentIdx. This gives us 1. Since it is lesser than float(‘inf’), we update step = 1. We continue such comparisons until we reach the end of the index. Again, we have to do this from the end of the index till the start of the index. At the end of the iteration, we store the result in the array we instantiated in the beginning if the steps needed for that requirement is the highest so far. We continue doing this for the remainder of the requirements and the remainder of the blocks. At the end, we return the index which holds the minimum value of steps which is the block that is the optimal apartment we are looking for.

What is the time and space complexity? The time complexity is O(b²r) and space complexity is O(b) where b is the length of the list of blocks and r is the length of the list of requirements. The time complexity is O(b²r) because in total we are doing three iterations, once through the list of blocks, once through the list of requirements, and another through the list of blocks again. The space complexity is O(b) because we instantiate an array of length equal to the length of the list of blocks.

After determining the time and space complexity, the next question every aspiring algorithm guru should ask is… Can we do better?

Indeed we can.

Suppose that we are given an array of where the distance of the nearest requirement was already computed.

distances = [
    [1, 0, 0, 1, 2],
    [0, 1, 0, 0, 0],
    [4, 3, 2, 1, 0]
]

0           1            2             3            4
school                 school       school         school
           gym         gym                         
                                                   clinic

The distances array represent the minimum steps for each requirement. For block at index 0, the gym is 1 step away, the school is 0 steps away and the clinic is 4 steps away.

If somehow we can compute the minimum distances of each requirement beforehand, we could easily just take the maximum of the distances to derive our most optimal apartment.

An example solution would look like this.

def apartmentHunting(blocks, reqs):
    distances = [[float('inf') for _ in range(len(blocks))] for _ in reqs]
    result = [float('-inf') for _ in range(len(blocks))]
    for reqIdx, req in enumerate(reqs):
        
        nearestReqIdx = None
        for blkIdx, block in enumerate(blocks):
            if block[req]:
                nearestReqIdx = blkIdx
            if nearestReqIdx is not None:
                distances[reqIdx][blkIdx] = min(distances[reqIdx][blkIdx], blkIdx - nearestReqIdx)   
        
        nearestReqIdx = None
        for blkIdx in range(len(blocks) - 1, -1, -1):
            block = blocks[blkIdx]
            if block[req]:
                nearestReqIdx = blkIdx
            if nearestReqIdx is not None:
                distances[reqIdx][blkIdx] = min(distances[reqIdx][blkIdx], nearestReqIdx - blkIdx) 
        
        for blkIdx in range(len(blocks)):
            result[blkIdx] = max(result[blkIdx], distances[reqIdx][blkIdx])
    return result.index(min(result))

We first instantiate an array of dimensions of length of list of blocks by the length of list of requirements. Also, same as before, an array call results equal to the length of list of blocks. We iterate through the list of requirements, at each requirement, we iterate through the blocks from the start to the end, then back to the start, to find the minimum distance of the requirement for that block. Then, we update the maximum of the steps for each block. At the end, we return the index of the minimum value of the results array which gives the apartment that we are looking for.

The time complexity is O(br) as we are computing the distances array by iterating through the list of requirements, and at each requirement iterating through the list of blocks.