Tallest building between parking lots

Model. Every usable tile ('P' or '-') gets a height. Parking lots have height 0. Two usable tiles that share an edge may differ in height by at most 1. 'X' tiles hold nothing and carry no rule, so they act as walls. We want the tallest building we can legally put anywhere on the grid.

Upper bound. Take any building tile v and a shortest path of usable tiles from v to some parking lot, of length d(v). Each step along the path can raise the height by at most 1, starting from 0 at the lot. So height(v) <= d(v). This is true for every lot, so the bound is the distance to the nearest lot.

The bound is reachable. Set height(v) = d(v) for every tile at once. For two neighbours u and v, the triangle inequality gives |d(u) - d(v)| <= 1, so the whole assignment is legal. Every tile hits its own upper bound at the same time, so the answer is max d(v).

Brute force. Run a BFS from each building tile until it finds a lot. With B buildings on an R x C grid that is O(B * R * C), up to O((RC)^2). Candidates often start here, and it is a fine thing to say out loud before improving it.

Optimal: multi-source BFS. Put every 'P' in the queue at distance 0 and expand outward, skipping 'X'. The first time BFS reaches a tile is its distance to the nearest lot, because BFS visits tiles in order of distance from the set of sources. One pass over the grid gives every d(v).

Edge cases that need a decision (state them to the interviewer).

• A building region walled off by 'X' with no lot in it has no upper bound. We return -1 for "unbounded".
• No building tiles at all: the answer is 0 (the tallest thing is a parking lot). An empty grid also returns 0.

Invariant. When a tile is popped from the queue, its stored distance is final and equals the shortest usable-tile path to any lot. Distances in the queue never decrease and differ by at most 1 from front to back.

from collections import deque
from typing import List, Optional

PARKING, BUILD, BLOCKED = "P", "-", "X"
UNBOUNDED = -1


def height_map(grid: List[str]) -> List[List[Optional[int]]]:
    """Max legal height for each tile.

    Parking -> 0, 'X' -> None, buildings -> distance to nearest lot,
    or UNBOUNDED (-1) when no lot is reachable.
    """
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    dist: List[List[Optional[int]]] = [[None] * cols for _ in range(rows)]
    queue: deque = deque()

    for r in range(rows):
        if len(grid[r]) != cols:
            raise ValueError("grid must be rectangular")
        for c in range(cols):
            ch = grid[r][c]
            if ch not in (PARKING, BUILD, BLOCKED):
                raise ValueError(f"bad tile {ch!r} at ({r}, {c})")
            if ch == PARKING:
                dist[r][c] = 0
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if (
                0 <= nr < rows
                and 0 <= nc < cols
                and grid[nr][nc] == BUILD
                and dist[nr][nc] is None
            ):
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == BUILD and dist[r][c] is None:
                dist[r][c] = UNBOUNDED
    return dist


def max_building_height(grid: List[str]) -> int:
    """Tallest legal building anywhere; -1 if some building is unbounded."""
    best = 0
    for row in height_map(grid):
        for h in row:
            if h == UNBOUNDED:
                return UNBOUNDED
            if h is not None:
                best = max(best, h)
    return best


if __name__ == "__main__":
    assert max_building_height(["P--", "---", "--P"]) == 2
    assert max_building_height(["P----"]) == 4
    assert max_building_height(["P-X--", "--X-P"]) == 2
    assert max_building_height(["PX-"]) == UNBOUNDED
    assert max_building_height(["PPP", "PPP"]) == 0
    assert max_building_height(["XXX"]) == 0
    assert max_building_height([]) == 0
    assert max_building_height(["-"]) == UNBOUNDED
    # A wall forces a detour, so the far side is taller than its
    # straight-line distance suggests.
    assert max_building_height(["P-", "X-", "--", "-X", "--"]) == 7
    assert height_map(["P-", "X-"]) == [[0, 1], [None, 2]]
    print("all tests passed")

• Time: O(R * C). Each tile enters the queue at most once and checks 4 neighbours. The final scans are also O(R * C).
• Space: O(R * C) for the distance grid and the queue. If only the maximum is needed, the grid can be reused as the visited marker, but the queue still holds up to O(R * C) tiles in the worst case.
• Brute force (BFS per building): O(B * R * C) time, O(R * C) space.

• ["P--", "---", "--P"] -> 2 (centre and corners are 2 steps from a lot).
• ["P----"] -> 4 (a single row, height rises by 1 per tile).
• ["P-X--", "--X-P"] -> 2 (the X column splits the grid; each side has its own lot).
• ["PX-"] -> -1 (the right building cannot reach any lot, so it is unbounded).
• ["-"] -> -1 (no lots anywhere).
• ["PPP", "PPP"] -> 0 (no buildings).
• ["XXX"] -> 0; [] -> 0 (nothing usable).
• ["P-", "X-", "--", "-X", "--"] -> 7 (walls force a snake path; the last tile is 7 usable steps away).
• height_map(["P-", "X-"]) -> [[0, 1], [None, 2]].
• Large: a 1000 x 1000 grid of '-' with one 'P' in a corner -> 1998, in linear time.

1. Lots have fixed, nonzero heights h(p). The bound becomes min over p of h(p) + d(p, v). Run Dijkstra (or a 0-1 / bucket BFS keyed by height) seeded with each lot at its own height. Then check feasibility: two lots are inconsistent if |h(p) - h(q)| > d(p, q); detect it by checking, after the run, that every lot still has its own height (no lot got lowered by another).
2. Height difference up to k instead of 1, or per-tile height caps. With difference k, answer k * d(v). With a cap cap(v) on some tiles, treat every capped tile as an extra source with height cap(v) and use the same Dijkstra as in part 1. The answer is the min over all sources of source height + k * distance.
3. Diagonals count as adjacent. Use 8 neighbours. The distance becomes Chebyshev distance on an open grid; the BFS code changes only in the neighbour list.
4. Online updates: a tile becomes a new parking lot. Heights only go down. Run a BFS from the new lot that stops wherever the new distance is not strictly better than the stored one. The cost is proportional to the tiles that change. Removing a lot (heights go up) is harder; the simple answer is to recompute, and a stronger answer keeps the count of nearest lots per tile or rebuilds only the affected region.
5. Huge or sparse grid (lots and walls given as coordinates). Without walls, the answer is the largest Manhattan distance to the nearest lot, which can be found by binary search on the answer with a rotated-coordinate (x+y, x-y) coverage check, without touching every tile.

Mid-level (L4)

• Turns the rule "adjacent heights differ by at most 1" into "height is bounded by distance to the nearest lot", maybe after a hint.
• Writes a correct BFS that skips 'X' and stays in bounds.
• May start with BFS from every building, then moves to multi-source BFS when asked about cost.

Senior (L5)

• Gives both halves of the argument without prompting: the upper bound along a shortest path and why height = distance is legal everywhere at once.
• Goes straight to multi-source BFS and states O(R * C) time and space.
• Raises the edge cases (unreachable region, no lots, no buildings, empty grid) and agrees on return values before coding.
• Handles parts 1 and 2 (fixed lot heights, caps) by switching to Dijkstra from many sources.

Staff (L6+)

• Frames the problem as a shortest-path / Lipschitz-bound problem, so the follow-ups reduce to "change the sources and edge weights".
• Explains the feasibility check for conflicting fixed heights and the incremental update for a new lot, including why removal is harder.
• Discusses scale: memory for very large grids, the sparse coordinate variant, and splitting the grid into tiles processed in parallel with boundary exchange.