Campus Bikes II solution and explanation
Google
9 more videos on this problem
LeetCode 1066. Campus Bikes II Explanation and Solutionhappygirlzt · 13:11 · 4K views
LeetCode 1066. Campus Bikes II 中文解释 Chinese Versionhappygirlzt · 13:15 · 2K views
Campus Bikes II: Leetcode 1066Tony Teaches · 20:55 · 1K views
LeetCode 1066. Campus Bikes IIHappy Coding · 30:12 · 1K views
1066. Campus Bikes II - Week 3/5 Leetcode December ChallengeProgramming Live with Larry · 13:32 · 455 views
1066. Campus Bikes II - Week 1/5 Leetcode January ChallengeProgramming Live with Larry · 27:00 · 426 views
1066. Campus Bikes II - Week 1/5 Leetcode September ChallengeProgramming Live with Larry · 11:17 · 309 views
猩猩的乐园 Leetcode 1066 Campus Bikes II猩猩的乐园 · 15:00 · 293 views
LeetCode 1066 - Campus Bikes II - PythonAlpha-Code · 16:34 · 192 views
LeetCode #1066 - Campus Bikes IIRoel Van de Paar · 3:06 · 38 views
The problem
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] < 1000- All the workers and the bikes locations are unique.
Approach overview
Problem 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.
Solution
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
n, m = len(workers), len(bikes)
f = [[inf] * (1 << m) for _ in range(n + 1)]
f[0][0] = 0
for i, (x1, y1) in enumerate(workers, 1):
for j in range(1 << m):
for k, (x2, y2) in enumerate(bikes):
if j >> k & 1:
f[i][j] = min(
f[i][j],
f[i - 1][j ^ (1 << k)] + abs(x1 - x2) + abs(y1 - y2),
)
return min(f[n])class Solution {
public int assignBikes(int[][] workers, int[][] bikes) {
int n = workers.length;
int m = bikes.length;
int[][] f = new int[n + 1][1 << m];
for (var g : f) {
Arrays.fill(g, 1 << 30);
}
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 1 << m; ++j) {
for (int k = 0; k < m; ++k) {
if ((j >> k & 1) == 1) {
int d = Math.abs(workers[i - 1][0] - bikes[k][0])
+ Math.abs(workers[i - 1][1] - bikes[k][1]);
f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
}
}
}
}
return Arrays.stream(f[n]).min().getAsInt();
}
}class Solution {
public:
int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int n = workers.size(), m = bikes.size();
int f[n + 1][1 << m];
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 1 << m; ++j) {
for (int k = 0; k < m; ++k) {
if (j >> k & 1) {
int d = abs(workers[i - 1][0] - bikes[k][0]) + abs(workers[i - 1][1] - bikes[k][1]);
f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
}
}
}
}
return *min_element(f[n], f[n] + (1 << m));
}
};function assignBikes(workers: number[][], bikes: number[][]): number {
const n = workers.length;
const m = bikes.length;
const inf = 1 << 30;
const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(1 << m).fill(inf));
f[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j < 1 << m; ++j) {
for (let k = 0; k < m; ++k) {
if (((j >> k) & 1) === 1) {
const d =
Math.abs(workers[i - 1][0] - bikes[k][0]) +
Math.abs(workers[i - 1][1] - bikes[k][1]);
f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
}
}
}
}
return Math.min(...f[n]);
}func assignBikes(workers [][]int, bikes [][]int) int {
n, m := len(workers), len(bikes)
f := make([][]int, n+1)
const inf = 1 << 30
for i := range f {
f[i] = make([]int, 1<<m)
for j := range f[i] {
f[i][j] = inf
}
}
f[0][0] = 0
for i := 1; i <= n; i++ {
for j := 0; j < 1<<m; j++ {
for k := 0; k < m; k++ {
if j>>k&1 == 1 {
d := abs(workers[i-1][0]-bikes[k][0]) + abs(workers[i-1][1]-bikes[k][1])
f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+d)
}
}
}
}
return slices.Min(f[n])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| 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 |
Frequently asked questions
Is Campus Bikes II easy or hard?
Campus Bikes II is usually classified as a Medium problem. The brute force idea is straightforward, but recognizing the optimization using bitmask dynamic programming requires familiarity with subset DP and recursion with memoization.
Campus Bikes II Python/Java solution
The typical implementation uses DFS with memoization and a bitmask parameter. For each recursive call, iterate through bikes, skip those whose bit is set, compute the Manhattan distance, and update the minimum cost. This approach translates cleanly across Python, Java, C++, Go, and TypeScript.
How to solve Campus Bikes II in O(n * 2^m)?
Use a bitmask to represent which bikes are already assigned. The worker index equals the number of set bits in the mask. For each unused bike, compute the Manhattan distance to the current worker and recursively solve the next state. Cache results by mask to avoid recomputation.
What is the best approach for Campus Bikes II?
The most efficient approach is dynamic programming with bitmasking and memoized DFS. Represent assigned bikes with a bitmask and derive the worker index from the number of set bits. For each state, try assigning an unused bike and store the minimum cost. This reduces the search from factorial permutations to about O(n * 2^m).
Is Campus Bikes II asked at Google/Amazon/Meta?
Campus Bikes II is a common interview-style problem involving assignment optimization and bitmask DP. Variants of this problem have appeared in interviews at companies like Google, Amazon, and Meta because they test recursion, dynamic programming, and state compression techniques.
What data structure is used in Campus Bikes II?
The key structure is a bitmask integer representing which bikes are already assigned. A hash map or array is used for memoization of DP states. The solution also relies on arrays to store worker and bike coordinates.
What is the time complexity of Campus Bikes II?
The optimized solution runs in O(n * 2^m) time, where n is the number of workers and m is the number of bikes. Each bitmask represents a subset of bikes already assigned, and for each state you iterate through possible bikes. Space complexity is O(2^m) for the memoization table.