LeetCode 1066: Campus Bikes II

Problem Restatement

We have n workers and m bikes on a campus.

We need to assign each worker exactly one bike, minimizing the total Manhattan distance between each worker and their assigned bike.

Return the minimum total Manhattan distance.

The official constraints state that n <= m <= 10 (small, bitmask DP is feasible).

Input and Output

Function shape:

def assignBikes(workers: list[list[int]], bikes: list[list[int]]) -> int:
    ...

Key Insight

With m <= 10 bikes, we can represent which bikes have been assigned using a bitmask.

dp[mask] = minimum cost to assign popcount(mask) workers to the bikes indicated by mask.

The i-th worker uses bike j when bit j is set in the mask.

Algorithm

1. dp[0] = 0.
2. For each mask (in order of popcount):
   • Let i = popcount(mask) (this is the worker index).
   • For each bike j not in the mask:
     • dp[mask | (1 << j)] = min(..., dp[mask] + dist(worker[i], bike[j])).
3. Return the minimum dp[mask] where popcount(mask) == n.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def assignBikes(self, workers: list[list[int]], bikes: list[list[int]]) -> int:
        n, m = len(workers), len(bikes)
        inf = float("inf")
        dp = [inf] * (1 << m)
        dp[0] = 0

        def dist(w, b):
            return abs(w[0] - b[0]) + abs(w[1] - b[1])

        for mask in range(1 << m):
            worker_idx = bin(mask).count('1')
            if worker_idx >= n:
                continue
            for j in range(m):
                if not (mask >> j & 1):
                    new_mask = mask | (1 << j)
                    dp[new_mask] = min(dp[new_mask], dp[mask] + dist(workers[worker_idx], bikes[j]))

        return min(dp[mask] for mask in range(1 << m) if bin(mask).count('1') == n)

Testing

def run_tests():
    s = Solution()

    assert s.assignBikes([[0,0],[2,1]], [[1,2],[3,3],[2,3]]) == 6
    assert s.assignBikes([[0,0],[1,1],[2,0]], [[1,0],[2,2],[2,1]]) == 4

    print("all tests passed")

run_tests()