Problem Breakdown
We are tasked with a resource allocation problem on a grid. We have N workers and M bikes where . 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( points),bikes( points). - Constraints ensure . 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 (), some bikes will remain unassigned. We need to select the optimal subset of bikes from .
- 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 .
- Empty inputs are not possible per constraints ().
Intuition
A brute-force approach would involve trying every permutation of assigning bikes to workers. Since we need to pick bikes out of , the complexity is roughly proportional to permutations . For , 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 (), 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 ( choices for worker 1, for worker 2…). While acceptable for , 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).
-
State Definition:
worker_index: The current worker we are trying to assign a bike for ( to ).bike_mask: An integer bitmask where the -th bit is set if the -th bike has been assigned.
-
Base Case:
- If all workers have been processed (
worker_index == N), return 0 (no more distance to add).
- If all workers have been processed (
-
Recursive Step:
- For the current
worker_index, iterate through every available bike ( from to ) that is not yet used inbike_mask. - Calculate Manhattan distance between
workers[worker_index]andbikes[j]. - Recursively call for the next worker (
worker_index + 1) with an updated mask (bit set).
- For the current
-
Memoization:
- Store the result of
(worker_index, bike_mask)to avoid recalculating costs when we reach the same state via different paths.
- Store the result of
-
Optimization Note: Since
worker_indexis implicitly determined by the number of bits set inbike_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 orlru_cache.
Complexity Analysis
- Time Complexity: .
- There are roughly states at depth (where is the number of workers assigned). Summing over all depths, and considering we iterate through available bikes (), it fits well within limits for .
- More precisely, the state space size is bounded by which is less than . For each state we do work proportional to available bikes. With memoization, it’s efficient enough for these constraints.
- Space Complexity: (or just ) to store the DP table/memoization cache plus recursion stack depth of .
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
- : 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 bikes from .