Apartment Hunting

Tags

Apartment Hunting

Category

Arrays

Difficulty

Very Hard

Problem Statement

You are given a list of blocks, where each block contains information about the presence of certain buildings (e.g., gym, school, store). You are also given a list of required buildings. Find the block index that minimizes the farthest distance you would have to walk to reach all required buildings. In other words, for each block, compute the maximum distance to the nearest instance of each required building, then return the block that minimizes that maximum distance.

Intuition

A brute-force approach would check, for every block, the closest instance of each required building, taking O(b * r * b) time where b is the number of blocks and r is the number of requirements. We can do better by precomputing, for each required building, the closest distance from every block. By making two linear passes — one forward and one backward — we can fill in the minimum distance to each building type for every block in O(b) per building. This works because the nearest building is either to the left (captured by the forward pass) or to the right (captured by the backward pass).

Approach

  1. For each required building, create an array of size n (number of blocks) that will hold the minimum distance from block i to the nearest occurrence of that building.
  2. Forward pass: Traverse blocks left to right. Track the last-seen index for the building. If the building exists at block i, distance is 0; otherwise, it is i - lastSeen (or infinity if not yet seen).
  3. Backward pass: Traverse blocks right to left. Track the last-seen index from the right. Take the minimum of the forward-pass value and lastSeen - i.
  4. After computing min-distance arrays for all required buildings, iterate over each block. For each block, the "cost" is the maximum value across all requirement arrays at that index.
  5. Return the block index with the smallest cost.

Pseudocode

function apartmentHunting(blocks, reqs):
    minDistances = []
    for each req in reqs:
        distances = array of size len(blocks), filled with MAX_INT

        # Forward pass
        lastSeen = -MAX_INT
        for i from 0 to len(blocks) - 1:
            if blocks[i][req] is true:
                lastSeen = i
            distances[i] = i - lastSeen

        # Backward pass
        lastSeen = MAX_INT
        for i from len(blocks) - 1 downto 0:
            if blocks[i][req] is true:
                lastSeen = i
            distances[i] = min(distances[i], lastSeen - i)

        minDistances.append(distances)

    # Find the block minimizing the max distance across all reqs
    bestBlock = 0
    bestCost = MAX_INT
    for i from 0 to len(blocks) - 1:
        cost = max(minDistances[r][i] for r in range(len(reqs)))
        if cost < bestCost:
            bestCost = cost
            bestBlock = i
    return bestBlock

Time & Space Complexity

  • Time: O(b * r) where b is the number of blocks and r is the number of required buildings. Each building requires two O(b) passes, and the final scan is O(b * r).
  • Space: O(b * r) to store the precomputed distance arrays. This can be reduced to O(b) by processing one requirement at a time and keeping a running max per block.

Key Insights

  • The two-pass technique (forward + backward) is a classic pattern for computing nearest distances in linear time. It appears in many array problems.
  • The problem reduces to a minimax optimization: minimize over blocks the maximum over requirements.
  • Precomputation decouples the requirements from the block scan, turning a cubic approach into a quadratic one (and effectively linear for small r).

Edge Cases

  • Only one block: return index 0 regardless of requirements.
  • A required building exists at every block: distance for that requirement is 0 everywhere.
  • A required building exists at only one block: distances radiate outward from that single block.
  • Multiple blocks tie for the optimal cost: any valid index is acceptable (typically return the first).
  • Empty requirements list: any block is optimal (return 0).

Linked mentions