On a campus represented on the X-Y plane, there are n workers and m bikes, with n <= m.
You are given an array workers of length n where workers[i] = [xi, yi] is the position of the ith worker. You are also given an array bikes of length m where bikes[j] = [xj, yj] is the position of the jth bike. All the given positions are unique.
Assign a bike to each worker. Among the available bikes and workers, we choose the (workeri, bikej) pair with the shortest Manhattan distance between each other and assign the bike to that worker.
If there are multiple (workeri, bikej) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index. If there are multiple ways to do that, we choose the pair with the smallest bike index. Repeat this process until there are no available workers.
Return an array answer of length n, where answer[i] is the index (0-indexed) of the bike that the ith worker is assigned to.
The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Example 1:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0] Explanation: Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].
Example 2:
Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Output: [0,2,1] Explanation: Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].
Constraints:
n == workers.lengthm == bikes.length1 <= n <= m <= 1000workers[i].length == bikes[j].length == 20 <= xi, yi < 10000 <= xj, yj < 1000Problem Overview: You are given coordinates of workers and bikes on a 2D grid. Assign exactly one bike to each worker so that assignments follow the smallest Manhattan distance first. If multiple pairs have the same distance, choose the smaller worker index, then the smaller bike index.
Approach 1: All Pairs + Sorting (O(WB log(WB)) time, O(WB) space)
Compute the Manhattan distance for every worker–bike pair using |x1-x2| + |y1-y2|. Store tuples like (distance, workerIndex, bikeIndex) in a list. Sort this list so the smallest distance appears first, with worker and bike indices acting as tie-breakers. Iterate through the sorted pairs and greedily assign bikes if the worker and bike are both still unassigned.
This works because sorting guarantees pairs are processed in the correct priority order. You maintain two arrays: one to track assigned bikes and another to store the final bike index for each worker. The approach is straightforward and reliable, though generating all pairs costs O(WB) space and sorting dominates runtime.
Approach 2: Bucket Sort by Distance (O(WB + D) time, O(WB + D) space)
The Manhattan distance range is limited (0–2000 based on constraints). Instead of sorting all pairs, group them into buckets where index = distance. For every worker–bike pair, compute the distance and append the pair into buckets[distance]. Then iterate distances from smallest to largest and greedily assign pairs while both the worker and bike remain free.
This avoids the log factor from sorting because pairs are already grouped by distance. The algorithm still checks every worker–bike pair, but processing the buckets is linear relative to the distance range. This makes the runtime effectively O(WB + D), which is faster in practice for larger inputs.
Both strategies rely on a greedy decision: assign the closest available pair first. The tie-breaking rule is naturally preserved because worker and bike indices are processed in order inside each distance group.
Recommended for interviews: The bucket-based greedy approach shows stronger algorithmic awareness because it removes the sorting overhead using the bounded Manhattan distance property. However, the pair-generation + sorting solution is often accepted in interviews and easier to implement correctly. Understanding both demonstrates comfort with array processing, greedy assignment strategies, and optimization through sorting techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| All Pairs + Sorting | O(WB log(WB)) | O(WB) | Simple and reliable implementation when constraints are moderate |
| Bucket Sort by Distance | O(WB + D) | O(WB + D) | Best when distance range is bounded and you want to avoid sorting |
LeetCode 1057. Campus Bikes Explanation and Solution • happygirlzt • 5,714 views views
Watch 9 more video solutions →Practice Campus Bikes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor