Problem Description

You have n workers and m bikes positioned on a 2D coordinate plane (where n ≤ m). Each worker needs to be assigned exactly one bike.

Input:

• workers[i] = [xi, yi] represents the position of the i-th worker
• bikes[j] = [xj, yj] represents the position of the j-th bike
• All positions are unique

Assignment Rules:

1. Calculate the Manhattan distance between each worker-bike pair: |worker.x - bike.x| + |worker.y - bike.y|
2. Assign bikes using these priorities:
   • Choose the worker-bike pair with the shortest Manhattan distance
   • If multiple pairs have the same distance, choose the pair with the smallest worker index
   • If still tied, choose the pair with the smallest bike index
3. Once a worker is assigned a bike, both become unavailable for future assignments
4. Repeat until all workers have bikes

Output: Return an array answer where answer[i] is the index of the bike assigned to worker i.

Example: If you have workers at positions [[0,0], [2,1]] and bikes at [[1,2], [3,3]]:

• Worker 0 to Bike 0: distance = |0-1| + |0-2| = 3
• Worker 0 to Bike 1: distance = |0-3| + |0-3| = 6
• Worker 1 to Bike 0: distance = |2-1| + |1-2| = 2
• Worker 1 to Bike 1: distance = |2-3| + |1-3| = 3

The smallest distance is 2 (Worker 1 to Bike 0), so Worker 1 gets Bike 0. Then Worker 0 gets the remaining Bike 1. Result: [1, 0].

Intuition

The key insight is that this is a greedy assignment problem where we need to make optimal local choices based on a specific priority order. Since we want to assign bikes to workers following strict rules (shortest distance first, then worker index, then bike index), we can think of this as processing all possible worker-bike pairs in a sorted order.

The natural approach is to:

1. Generate all possible pairings: Since we need to consider every worker with every bike, we create all n × m possible combinations
2. Sort by priority: Instead of repeatedly searching for the minimum distance pair, we can sort all pairs once according to our criteria
3. Greedily assign: Process pairs in sorted order and make assignments when both the worker and bike are still available

Why does greedy work here? Because once we've sorted all pairs by (distance, worker_index, bike_index), the first valid pair we encounter for any worker will always be their optimal assignment according to the problem's rules. There's no benefit in "saving" a bike for a different worker since we're already processing in the globally optimal order.

The sorting naturally handles all tiebreakers:

• Python's sort is stable and compares tuples element by element
• A tuple (distance, worker_id, bike_id) will automatically sort by distance first, then worker index, then bike index

This transforms a potentially complex matching problem into a simple: sort everything, then iterate and assign. The time complexity is dominated by sorting O(nm log(nm)), which is acceptable given the problem constraints.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a straightforward greedy approach with sorting:

Step 1: Generate All Pairs with Distances

arr = []
for i, j in product(range(n), range(m)):
    dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
    arr.append((dist, i, j))

• Use itertools.product to generate all (worker_index, bike_index) combinations
• Calculate Manhattan distance for each pair: |x1 - x2| + |y1 - y2|
• Store each combination as a tuple (distance, worker_index, bike_index)

Step 2: Sort the Pairs

arr.sort()

• Python sorts tuples lexicographically (element by element)
• This automatically gives us the correct priority order:
  • Primary: shortest distance
  • Secondary: smallest worker index
  • Tertiary: smallest bike index

Step 3: Track Assignments

vis1 = [False] * n  # Track assigned workers
vis2 = [False] * m  # Track assigned bikes
ans = [0] * n       # Store bike assignment for each worker

• Use boolean arrays to mark workers and bikes as "used"
• Initialize result array to store final assignments

Step 4: Greedy Assignment

for _, i, j in arr:
    if not vis1[i] and not vis2[j]:
        vis1[i] = vis2[j] = True
        ans[i] = j

• Iterate through sorted pairs in order
• For each pair (distance, worker_i, bike_j):
  • Check if both worker i and bike j are available
  • If yes, make the assignment: worker i gets bike j
  • Mark both as used to prevent reassignment
• Skip pairs where either the worker or bike is already assigned

Time Complexity: O(nm log(nm)) for generating and sorting all pairs Space Complexity: O(nm) for storing all pairs

The algorithm guarantees optimal assignments because we process pairs in the exact priority order specified by the problem. Once a worker is assigned, we never need to reconsider that assignment since we've already evaluated all better options.

Example Walkthrough

Let's walk through a small example with 2 workers and 3 bikes:

• Workers: [[0,0], [1,1]]
• Bikes: [[0,1], [4,2], [2,1]]

Step 1: Calculate all worker-bike distances

Step 2: Sort all pairs by (distance, worker_index, bike_index)

Sorted list:

1. (1, 0, 0) - Worker 0 to Bike 0, distance 1
2. (1, 1, 0) - Worker 1 to Bike 0, distance 1 (tied distance, worker 1 > 0)
3. (1, 1, 2) - Worker 1 to Bike 2, distance 1 (tied distance & worker)
4. (3, 0, 2) - Worker 0 to Bike 2, distance 3
5. (4, 1, 1) - Worker 1 to Bike 1, distance 4
6. (6, 0, 1) - Worker 0 to Bike 1, distance 6

Step 3: Process pairs greedily

Initialize:

• vis1 = [False, False] (workers availability)
• vis2 = [False, False, False] (bikes availability)
• ans = [_, _] (assignments)

Processing:

1. (1, 0, 0): Worker 0 and Bike 0 both available

   • Assign: Worker 0 gets Bike 0
   • Update: vis1 = [True, False], vis2 = [True, False, False], ans = [0, _]

2. (1, 1, 0): Worker 1 available but Bike 0 already taken

   • Skip

3. (1, 1, 2): Worker 1 and Bike 2 both available

   • Assign: Worker 1 gets Bike 2
   • Update: vis1 = [True, True], vis2 = [True, False, True], ans = [0, 2]

4. All workers assigned, stop processing

Final Result: [0, 2]

• Worker 0 is assigned Bike 0
• Worker 1 is assigned Bike 2

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m * log(n * m))

• Creating the array arr: We iterate through all possible combinations of workers and bikes using product(range(n), range(m)), which generates n * m pairs. For each pair, we calculate the Manhattan distance and append to the array. This takes O(n * m) time.
• Sorting the array: The arr.sort() operation sorts n * m elements, which takes O(n * m * log(n * m)) time.
• Iterating through the sorted array: We iterate through all n * m elements once to assign bikes to workers. Each iteration involves constant time operations (checking and updating boolean arrays, assigning values). This takes O(n * m) time.
• Overall time complexity is dominated by the sorting step: O(n * m * log(n * m))

Space Complexity: O(n * m)

• The array arr stores n * m tuples, where each tuple contains 3 integers (distance, worker index, bike index). This requires O(n * m) space.
• Two boolean arrays vis1 and vis2 of sizes n and m respectively, requiring O(n + m) space.
• The answer array ans of size n, requiring O(n) space.
• Overall space complexity is dominated by the arr array: O(n * m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting Priority Queue/Heap Approach

A common mistake is trying to use a min-heap to avoid sorting all pairs upfront:

Incorrect Approach:

import heapq

def assignBikes_wrong(workers, bikes):
    heap = []
    for i in range(len(workers)):
        for j in range(len(bikes)):
            dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
            heapq.heappush(heap, (dist, i, j))
  
    result = [0] * len(workers)
    worker_assigned = [False] * len(workers)
    bike_assigned = [False] * len(bikes)
  
    while heap:
        dist, w, b = heapq.heappop(heap)
        if not worker_assigned[w] and not bike_assigned[b]:
            worker_assigned[w] = bike_assigned[b] = True
            result[w] = b
  
    return result

Why This Fails: While this looks more efficient, it produces the same O(nm log(nm)) complexity since we still push all pairs to the heap. The heap doesn't provide any advantage here because we need to consider all pairs in sorted order anyway.

2. Misunderstanding Assignment Priority

Developers often incorrectly assume they should find the best bike for each worker independently:

Incorrect Approach:

def assignBikes_wrong(workers, bikes):
    result = []
    used_bikes = set()
  
    for i, worker in enumerate(workers):
        best_bike = -1
        best_dist = float('inf')
      
        for j, bike in enumerate(bikes):
            if j not in used_bikes:
                dist = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
                if dist < best_dist:
                    best_dist = dist
                    best_bike = j
      
        result.append(best_bike)
        used_bikes.add(best_bike)
  
    return result

Why This Fails: This assigns bikes worker by worker, but the problem requires global optimization. A worker with a lower index might need to wait for a farther bike if another worker has a closer distance to their optimal bike.

3. Distance Constraint Optimization (Bucket Sort)

Some try to optimize using the bounded distance property (maximum Manhattan distance ≤ 2000):

Overengineered Approach:

def assignBikes_bucket(workers, bikes):
    # Bucket sort approach - technically correct but overcomplicated
    buckets = [[] for _ in range(2001)]  # Max possible distance
  
    for i in range(len(workers)):
        for j in range(len(bikes)):
            dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
            buckets[dist].append((i, j))
  
    # Sort within each bucket by worker index, then bike index
    for bucket in buckets:
        bucket.sort()
  
    # Process buckets in order
    result = [0] * len(workers)
    worker_assigned = [False] * len(workers)
    bike_assigned = [False] * len(bikes)
  
    for dist in range(2001):
        for w, b in buckets[dist]:
            if not worker_assigned[w] and not bike_assigned[b]:
                worker_assigned[w] = bike_assigned[b] = True
                result[w] = b
  
    return result

Why This is Problematic: While this achieves O(nm) time complexity by avoiding comparison-based sorting, it:

• Requires knowledge of the distance constraint (not always given)
• Uses more memory for sparse buckets
• Is harder to understand and maintain
• The performance gain is minimal for typical input sizes

4. Forgetting Edge Cases

Not handling the case where n = m (equal workers and bikes):

Solution: The original approach handles this correctly since every worker will get exactly one bike when n ≤ m is guaranteed.

Best Practice Solution:

Stick with the simple sorting approach from the original solution. It's clear, correct, and efficient enough for the problem constraints. The code is maintainable and doesn't require special knowledge about distance bounds.