LeetCode 1057: Campus Bikes

Problem Restatement

We have a campus as a 2D grid. We are given the positions of n workers and m bikes.

We need to assign one bike to each worker.

We assign bikes greedily:

1. Find the pair (worker, bike) with the smallest Manhattan distance.
2. Assign that bike to that worker.
3. Remove both from consideration.
4. Repeat.

If there are ties in distance, pick the smallest worker index, then smallest bike index.

Return an array where result[i] is the bike index assigned to worker i.

The official constraints state that 0 <= workers.length <= 1000 and 0 <= bikes.length <= 1000.

Input and Output

Function shape:

def assignBikes(workers: list[list[int]], bikes: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]

Distances: (0,0)→(1,2): 3, (0,0)→(3,3): 6, (2,1)→(1,2): 2, (2,1)→(3,3): 3.

Minimum is 2: worker 1 gets bike 0. Then worker 0 gets bike 1.

Answer:

[1, 0]

Key Insight

Compute all (distance, worker_idx, bike_idx) triples, sort them, then greedily assign.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def assignBikes(self, workers: list[list[int]], bikes: list[list[int]]) -> list[int]:
        pairs = []
        for i, (wr, wc) in enumerate(workers):
            for j, (br, bc) in enumerate(bikes):
                dist = abs(wr - br) + abs(wc - bc)
                pairs.append((dist, i, j))

        pairs.sort()
        assigned_worker = set()
        assigned_bike = set()
        result = [-1] * len(workers)

        for dist, w, b in pairs:
            if w not in assigned_worker and b not in assigned_bike:
                result[w] = b
                assigned_worker.add(w)
                assigned_bike.add(b)
                if len(assigned_worker) == len(workers):
                    break

        return result

Testing

def run_tests():
    s = Solution()

    assert s.assignBikes([[0,0],[2,1]], [[1,2],[3,3]]) == [1, 0]
    assert s.assignBikes([[0,0],[1,1],[2,0]], [[1,0],[2,2],[2,1]]) == [0, 2, 1]

    print("all tests passed")

run_tests()