Skip to main content
Talentd

Campus Bikes II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic ProgrammingBacktrackingBit Manipulation5 min readAsked at: Google
Practice this problem

Problem Statement

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.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

LeetCode 1066. Campus Bikes II Explanation and Solution • happygirlzt • 4,135 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Campus Bikes