On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. Each worker and bike is a 2D coordinate on this grid.
We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.
Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
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: 6 Explanation: We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
Example 2:
Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Output: 4 Explanation: We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.
Example 3:
Input: workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]] Output: 4995
Constraints:
n == workers.lengthm == bikes.length1 <= n <= m <= 10workers[i].length == 2bikes[i].length == 20 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000Problem Overview: You are given coordinates of workers and bikes on a 2D grid. Each worker must be assigned exactly one bike. The goal is to minimize the total Manhattan distance between workers and their assigned bikes.
Approach 1: Backtracking (Brute Force Search) (Time: O(mPn), Space: O(n))
Try every possible assignment of bikes to workers. Start with the first worker, iterate through all bikes that are not yet used, assign one, and recursively continue with the next worker. Maintain a visited array to track which bikes are already taken. For each assignment, compute the Manhattan distance |x1-x2| + |y1-y2| and accumulate the cost. This explores all permutations of bikes chosen for workers, which grows quickly as mPn. The approach is straightforward and demonstrates the core search idea but becomes slow as the number of bikes increases.
Approach 2: Backtracking with Memoization using Bitmask (Time: O(n * 2^m), Space: O(2^m))
Represent the set of assigned bikes using a bitmask where the i-th bit indicates whether bike i is used. The worker index can be inferred from the number of bits set in the mask. For each state, iterate through all bikes and try assigning any unused bike to the current worker. Compute the distance and recursively solve the remaining assignment. Use a memo table keyed by the mask to avoid recomputing states. This converts the brute-force permutation search into a dynamic programming problem over subsets.
The key insight: once a specific set of bikes has already been assigned, the remaining optimal cost is always the same regardless of how you reached that state. Memoizing by mask avoids exponential recomputation. The total number of states is 2^m, and each state tries up to m bikes.
This solution relies heavily on bitmask representation and subset DP. It is a classic example of combining backtracking with dynamic programming to reduce repeated work.
Recommended for interviews: Backtracking with memoization using a bitmask. Interviewers expect you to recognize that brute force explores permutations and then optimize it using subset DP. Showing the plain backtracking first demonstrates understanding of the assignment search space, while the bitmask DP shows strong algorithmic optimization skills.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking (Brute Force) | O(mPn) | O(n) | Useful for understanding the assignment search space or when constraints are very small |
| Backtracking + Memoization (Bitmask DP) | O(n * 2^m) | O(2^m) | Best general solution for n,m ≤ 10; avoids recomputation using subset DP |
LeetCode 1066. Campus Bikes II Explanation and Solution • happygirlzt • 4,130 views views
Watch 8 more video solutions →Practice Campus Bikes II with our built-in code editor and test cases.
Practice on FleetCode