Skip to main content
Talentd

Campus Bikes - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySorting6 min readAsked at: Oracle, Snowflake, Google
Practice this problem

Problem Statement

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.length
  • m == bikes.length
  • 1 <= n <= m <= 1000
  • workers[i].length == bikes[j].length == 2
  • 0 <= xi, yi < 1000
  • 0 <= xj, yj < 1000
  • All worker and bike locations are unique.

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
All Pairs + SortingO(WB log(WB))O(WB)Simple and reliable implementation when constraints are moderate
Bucket Sort by DistanceO(WB + D)O(WB + D)Best when distance range is bounded and you want to avoid sorting

Video Solution

LeetCode 1057. Campus Bikes Explanation and Solution • happygirlzt • 5,730 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Campus Bikes easy or hard?
Campus Bikes is generally classified as a Medium problem. The greedy logic is straightforward, but handling tie-breaking rules and optimizing from sorting to bucket grouping requires careful implementation.
Campus Bikes Python/Java solution
Most Python and Java implementations compute all worker-bike pairs, store tuples containing distance and indices, then sort them. A greedy loop assigns the first valid pair where both the worker and bike are free. The same logic translates directly to C++ and Go using vectors or slices.
How to solve Campus Bikes in O(WB + D)?
Compute the Manhattan distance for every worker-bike pair and place the pair in a bucket indexed by that distance. Iterate through buckets from smallest distance to largest and assign bikes greedily when both worker and bike are unassigned. This avoids sorting and processes pairs in linear order relative to the distance range.
What is the best approach for Campus Bikes?
The most efficient approach uses bucket sort based on Manhattan distance. Since the distance range is limited, worker-bike pairs can be grouped into distance buckets and processed from smallest to largest. This produces a time complexity of O(WB + D), avoiding the O(WB log(WB)) sorting cost.
Is Campus Bikes asked at Google/Amazon/Meta?
Campus Bikes has appeared in interviews at companies like Google because it tests greedy reasoning and careful tie-breaking rules. Candidates must handle pair generation, sorting or bucketing, and correct assignment logic under constraints.
What data structure is used in Campus Bikes?
Typical implementations use arrays or lists to store worker-bike pairs and a greedy assignment structure. The optimized solution also uses bucket arrays indexed by Manhattan distance to group pairs efficiently before processing.
What is the time complexity of Campus Bikes?
The common solution that generates all worker-bike pairs and sorts them runs in O(WB log(WB)) time with O(WB) space. An optimized bucket-based greedy solution improves runtime to O(WB + D), where D is the maximum Manhattan distance range.

Ready to solve this problem?

Practice Campus Bikes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Campus Bikes II