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.

Description Hints 1 Solution Video 13:11

1066. Campus Bikes II

Medium55.9% acceptance1 companyPremium elsewhere, free here

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.length
m == bikes.length
1 <= n <= m <= 10
workers[i].length == 2
bikes[i].length == 2
0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All the workers and the bikes locations are unique.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Model the problem with a dp(pos, mask) where pos represents the current bike to be assigned and mask the set of available workers.

13:11

Still stuck?Read the written solution, or watch a walkthrough.

Open solution