Count warehouse robots boxed in on all four sides

Clarify first. The input is two equal-length lists x and y; robot i sits at (x[i], y[i]). Pin down two things before coding:

• "Directly above" means same column, any distance. A robot at (x, y) has a robot above it if some robot sits at (x, y') with y' > y. It does not have to be the neighbour cell. This is the version candidates report; ask anyway, because the adjacent-cell version is a different (easier) problem.
• Positions are unique. No two robots share a point, so there is no tie-breaking.

Brute force. For every robot, scan every other robot and set four flags: up, down, left, right. Count the robots with all four set. This is O(n^2) and fine for a few thousand robots, but OA limits usually go to 10^5.

Optimal: extremes per row and column. A robot has someone above it exactly when it is not the topmost robot in its column. It has someone below when it is not the bottommost. The same holds for left and right in its row. So we only need four numbers:

• for each column x: the smallest and largest y in it;
• for each row y: the smallest and largest x in it.

One pass builds these maps. A second pass counts robots with col_min[x] < y < col_max[x] and row_min[y] < x < row_max[y].

Why it works. The strict inequalities are the whole proof. y < col_max[x] means some robot in column x has a larger y, so there is one above. The other three checks are symmetric. Because positions are unique, a robot is never compared against itself as its own neighbour.

Invariant. After the first pass, col_min[x] and col_max[x] are the extremes of column x, and row_min[y] and row_max[y] are the extremes of row y. Both passes are O(n) with hash maps.

from __future__ import annotations


def count_idle_drives(x: list[int], y: list[int]) -> int:
    """Count robots that have another robot above, below, left and right.

    "Above" means same x and larger y, at any distance (likewise for the rest).
    Positions are assumed unique.
    """
    if len(x) != len(y):
        raise ValueError("x and y must have the same length")

    col_min: dict[int, int] = {}
    col_max: dict[int, int] = {}
    row_min: dict[int, int] = {}
    row_max: dict[int, int] = {}

    for xi, yi in zip(x, y):
        col_min[xi] = min(col_min.get(xi, yi), yi)
        col_max[xi] = max(col_max.get(xi, yi), yi)
        row_min[yi] = min(row_min.get(yi, xi), xi)
        row_max[yi] = max(row_max.get(yi, xi), xi)

    idle = 0
    for xi, yi in zip(x, y):
        has_vertical = col_min[xi] < yi < col_max[xi]
        has_horizontal = row_min[yi] < xi < row_max[yi]
        if has_vertical and has_horizontal:
            idle += 1
    return idle


def count_idle_drives_brute(x: list[int], y: list[int]) -> int:
    """O(n^2) reference used to check the fast version."""
    n = len(x)
    idle = 0
    for i in range(n):
        up = down = left = right = False
        for j in range(n):
            if i == j:
                continue
            if x[j] == x[i]:
                up |= y[j] > y[i]
                down |= y[j] < y[i]
            if y[j] == y[i]:
                right |= x[j] > x[i]
                left |= x[j] < x[i]
        if up and down and left and right:
            idle += 1
    return idle


if __name__ == "__main__":
    # 3x3 grid: only the centre is idle.
    gx = [i for i in range(3) for _ in range(3)]
    gy = [j for _ in range(3) for j in range(3)]
    assert count_idle_drives(gx, gy) == 1

    # Plus sign with long arms: centre idle, arms are not.
    px = [5, 5, 5, 2, 9]
    py = [0, 4, 8, 4, 4]
    assert count_idle_drives(px, py) == 1

    assert count_idle_drives([], []) == 0
    assert count_idle_drives([7], [7]) == 0
    assert count_idle_drives([0, 1, 2, 3], [0, 0, 0, 0]) == 0  # one row

    import random
    rng = random.Random(1)
    for _ in range(300):
        pts = list({(rng.randint(-4, 4), rng.randint(-4, 4)) for _ in range(rng.randint(0, 40))})
        xs = [p[0] for p in pts]
        ys = [p[1] for p in pts]
        assert count_idle_drives(xs, ys) == count_idle_drives_brute(xs, ys)
    print("ok")

• Time: O(n) expected. One pass builds four hash maps; a second pass checks each robot in O(1).
• Space: O(n) for the maps (at most one entry per distinct row and column).
• Brute force: O(n^2) time, O(1) extra space.

• 3x3 full grid at (0..2, 0..2) → 1 (only (1, 1)).
• Plus sign (5,0) (5,4) (5,8) (2,4) (9,4) → 1; the centre (5,4) has neighbours at distance 3 and 4, which still count.
• Empty input → 0.
• One robot → 0.
• All robots on one row → 0 (nobody has anyone above or below).
• 4x4 full grid → 4 (the inner 2x2 block).
• A robot with neighbours on three sides only, e.g. (1,1) with (1,0) (1,2) (0,1) → 0.
• Negative coordinates, e.g. the plus sign shifted by (-10, -10) → 1.
• Large input: 10^5 robots on a 316x316 grid → 314 * 314, runs in well under a second.

1. Adjacent cells only. "Directly above" now means (x, y+1). Put all points in a set and check the four neighbours: O(n) time, simpler code. Good to show you noticed the ambiguity.
2. Return which robots are idle, not just how many. Same pass; collect indices instead of incrementing a counter. Sort them if the caller wants a stable order.
3. Robots move or arrive over time (online updates). Keep, per column, a sorted container of y values (and per row, of x values). Add and remove are O(log k). A robot's idle status only depends on its row's and column's extremes, so when the min or max of a row or column changes, only the robots at the old and new extremes change status. Maintain a running count by re-checking those few robots.
4. Idle needs at least k robots on each side. Replace min/max with sorted lists per row and column. For each robot, its rank in its column gives the counts below and above, and its rank in its row gives left and right. O(n log n) total.
5. Distance limit d. A neighbour must be within d cells. Sort each column and row; for each robot check that its predecessor and successor in the sorted list are within d. O(n log n).

Mid-level (L4)

• Asks whether "above" means adjacent or any distance, and confirms positions are unique.
• Gets a correct brute force, then reaches the per-row/per-column min and max idea.
• Clean code with the strict inequalities right; tests a single robot and a single row.

Senior (L5)

• Explains why only the extremes matter and states O(n) time and space without prompting.
• Handles negative and very large coordinates by using hash maps, not arrays indexed by coordinate.
• Checks the fast version against the brute force on random small inputs.
• Adapts quickly to the adjacent-cell and "return the robots" variants.

Staff (L6+)

• Designs the online version: what changes when one robot moves, and why only extreme robots flip status.
• Generalizes to "at least k per side" and distance limits with sorted structures, with clear complexity.
• Talks about scale: sharding a large warehouse by region, and how rows and columns that span shards affect the answer.