Domain 2MediumMEDIUM

Campus Bikes II

LeetCode problem 1066: Campus Bikes II (medium).

Domain: medium•Updated: 2026-09-08
#Dynamic Programming#Backtracking

Problem Breakdown

We are tasked with a resource allocation problem on a grid. We have N workers and M bikes where N≤MN \le M. The goal is to create a one-to-one mapping for each worker (assigning exactly one unique bike) such that the total Manhattan distance across all assignments is minimized.

Inputs:

  • Two lists of 2D coordinates: workers (NN points), bikes (MM points).
  • Constraints ensure 1≤N≤M≤101 \le N \le M \le 10. Coordinates are non-negative integers up to 999.

Outputs:

  • A single integer representing the minimum total Manhattan distance sum.

Implicit Constraints & Edge Cases:

  • Since we must assign exactly one bike per worker, and there are more bikes than workers (M>NM > N), some bikes will remain unassigned. We need to select the optimal subset of NN bikes from MM.
  • Coordinates can be large (up to 1000), but since Manhattan distance is linear, overflow isn’t an issue with standard integers for sums up to ≈2×104\approx 2 \times 10^4.
  • Empty inputs are not possible per constraints (N≥1N \ge 1).

Intuition

A brute-force approach would involve trying every permutation of assigning bikes to workers. Since we need to pick NN bikes out of MM, the complexity is roughly proportional to permutations P(M,N)P(M, N). For M=10M=10, this is manageable but inefficient compared to dynamic programming if constraints were larger (e.g., up to 20).

Key Insight: This problem can be modeled as finding a Minimum Weight Perfect Matching in a bipartite graph. Given the small constraint (N,M≤10N, M \le 10), we don’t need complex min-cost max-flow algorithms. Instead, Backtracking with Memoization (Dynamic Programming) is ideal here. We process workers sequentially and track which bikes have been used via a bitmask.

Why Brute Force Fails: Without memoization, the recursion tree branches significantly (MM choices for worker 1, M−1M-1 for worker 2…). While acceptable for N=10N=10, it’s redundant to recompute costs for identical states of “used bikes”. Memoizing based on which bikes are used allows us to solve overlapping subproblems efficiently.

Approach

We will use a recursive Depth First Search (DFS) function with memoization: dfs(worker_index, bike_mask).

  1. State Definition:

    • worker_index: The current worker we are trying to assign a bike for (00 to N−1N-1).
    • bike_mask: An integer bitmask where the ii-th bit is set if the ii-th bike has been assigned.
  2. Base Case:

    • If all workers have been processed (worker_index == N), return 0 (no more distance to add).
  3. Recursive Step:

    • For the current worker_index, iterate through every available bike (jj from 00 to M−1M-1) that is not yet used in bike_mask.
    • Calculate Manhattan distance between workers[worker_index] and bikes[j].
    • Recursively call for the next worker (worker_index + 1) with an updated mask (bit jj set).
  4. Memoization:

    • Store the result of (worker_index, bike_mask) to avoid recalculating costs when we reach the same state via different paths.
  5. Optimization Note: Since worker_index is implicitly determined by the number of bits set in bike_mask, strictly speaking, only the mask might be needed if we enforce strict ordering, but including both makes the logic explicit and safer for interview explanation. We will use a dictionary or lru_cache.

Complexity Analysis

  • Time Complexity: O(N⋅M⋅2M)O(N \cdot M \cdot 2^M).
    • There are roughly (Mk)\binom{M}{k} states at depth kk (where kk is the number of workers assigned). Summing over all depths, and considering we iterate through available bikes (MM), it fits well within limits for N,M≤10N,M \le 10.
    • More precisely, the state space size is bounded by ∑i=0N−1(Mi)\sum_{i=0}^{N-1} \binom{M}{i} which is less than 2M2^M. For each state we do work proportional to available bikes. With memoization, it’s efficient enough for these constraints.
  • Space Complexity: O(N⋅2M)O(N \cdot 2^M) (or just O(2M)O(2^M)) to store the DP table/memoization cache plus recursion stack depth of NN.

Solution

class Solution:
    def minDistance(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        N = len(workers)
        M = len(bikes)
        
        # Precompute distances to avoid repeated calculation inside recursion? 
        # Given constraints are small (M<=10), calculating on fly is fine.
        # However, precomputing makes code cleaner and slightly faster.
        dist_matrix = [[abs(w[0] - b[0]) + abs(w[1] - b[1]) for w in workers] 
                       for _ in range(M)] 
        
        from functools import lru_cache
        
        @lru_cache(None)
        def dfs(worker_idx, mask):
            # Base case: All workers assigned
            if worker_idx == N:
                return 0
            
            min_cost = float('inf')
            
            for bike_idx in range(M):
                # Check if this bike is already used (bit set to 1)
                if not ((mask >> bike_idx) & 1):
                    cost = dist_matrix[bike_idx][worker_idx] + dfs(worker_idx + 1, mask | (1 << bike_idx))
                    min_cost = min(min_cost, cost)
            
            return min_cost
        
        # Initial call: worker index 0, no bikes used yet (mask 0)
        result = dfs(0, 0)
        
        # Clear cache if needed for multiple calls in local testing, 
        # though LeetCode creates a new instance usually.
        del dist_matrix 
        
        return result

Edge Cases Handled

  • N=MN=M: The logic naturally handles this as the mask will eventually fill up exactly when all workers are assigned.
  • Large Coordinates: Manhattan distance calculation uses standard integer arithmetic, which Python handles arbitrarily large integers (though here values fit in 32-bit).
  • Optimal Subset Selection: Since we iterate through all available bikes for each worker and take the minimum sum, the algorithm implicitly selects the optimal subset of NN bikes from MM.