LeetCode 1057 - Campus Bikes

This problem models a matching process between workers and bikes on a two dimensional grid. Each worker and each bike has a unique coordinate, and every worker must eventually receive exactly one bike.

leetcodemediumarraysortingheap-(priority-queue)

LeetCode Problem 1057

Difficulty: 🟡 Medium
Topics: Array, Sorting, Heap (Priority Queue)

Solution

LeetCode 1057 - Campus Bikes

Problem Understanding

This problem models a matching process between workers and bikes on a two dimensional grid. Each worker and each bike has a unique coordinate, and every worker must eventually receive exactly one bike. Since the number of bikes is at least the number of workers, a complete assignment is always possible.

The key detail is that assignments are not made independently for each worker. Instead, the problem defines a global process:

  1. Among all currently unassigned workers and currently available bikes, select the pair with the smallest Manhattan distance.
  2. Assign that bike to that worker.
  3. Remove both from future consideration.
  4. Repeat until every worker has a bike.

The Manhattan distance between two points is:

$$|x_1 - x_2| + |y_1 - y_2|$$

The problem also defines strict tie breaking rules. If multiple worker-bike pairs have the same distance:

  1. Choose the pair with the smaller worker index.
  2. If worker indices are also tied, choose the smaller bike index.

The output is an array where answer[i] is the index of the bike assigned to worker i.

The constraints are important for choosing the algorithm. Both the number of workers and bikes can be as large as 1000. That means there can be up to:

$$1000 \times 1000 = 1,000,000$$

possible worker-bike pairs. Any solution that repeatedly scans all pairs after every assignment becomes too slow.

A few edge cases are important to recognize early:

  • Multiple pairs may share the same Manhattan distance, so tie breaking must be implemented exactly as specified.
  • A bike can only be assigned once, even if it is the closest option for multiple workers.
  • A worker can only receive one bike.
  • Some workers may have many nearby bikes while others have very limited choices, so a greedy choice for one worker affects all later assignments.
  • Since all coordinates are unique, we never have duplicate points, but equal distances are still very common.

Approaches

Brute Force Approach

A direct simulation approach would repeatedly search through every currently valid worker-bike pair to find the best assignment.

At each step:

  1. Examine every unassigned worker.
  2. Examine every unused bike.
  3. Compute the Manhattan distance.
  4. Keep track of the best pair according to:
  • smallest distance
  • then smallest worker index
  • then smallest bike index
  1. Assign that pair.
  2. Repeat until all workers are assigned.

This approach is correct because it follows the problem statement exactly. However, it is inefficient because the full search is repeated after every assignment.

If there are n workers and m bikes, then each assignment step may inspect nearly n * m pairs, and we perform this process n times.

That leads to roughly:

$$O(n^2 \times m)$$

which becomes too expensive when both dimensions approach 1000.

Optimal Approach

The key observation is that the ordering rules are completely deterministic. Every worker-bike pair can be represented as:

$$(distance,\ workerIndex,\ bikeIndex)$$

If we generate all possible pairs once and sort them according to these rules, then we can process the pairs in sorted order.

Whenever we encounter a pair:

  • If the worker is still unassigned
  • And the bike is still unused

then we perform the assignment.

Because the pairs are processed globally in the exact priority order required by the problem, the first valid pair encountered is always the correct next assignment.

This avoids repeatedly rescanning all possibilities.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n² × m) O(1) Repeatedly scans all remaining pairs
Optimal O(n × m log(n × m)) O(n × m) Precomputes and sorts all worker-bike pairs

Algorithm Walkthrough

Step 1: Generate All Possible Pairs

For every worker and every bike:

  1. Compute the Manhattan distance.
  2. Store a tuple containing:
  • distance
  • worker index
  • bike index

This creates a complete list of all possible assignments.

We use tuples because Python and Go sorting naturally compares values lexicographically, which perfectly matches the tie breaking rules.

Step 2: Sort the Pairs

Sort all tuples in ascending order.

The sorting order becomes:

  1. Smaller distance first
  2. Smaller worker index first
  3. Smaller bike index first

After sorting, the pairs appear exactly in the order required by the problem statement.

Step 3: Track Assignments

Maintain:

  • An answer array initialized to -1
  • A set or boolean array tracking used bikes
  • A counter for assigned workers

This allows us to efficiently determine whether a worker or bike is already taken.

Step 4: Process Pairs in Sorted Order

Iterate through the sorted list.

For each pair:

  1. Check whether the worker already has a bike.
  2. Check whether the bike is already used.
  3. If both are free:
  • assign the bike
  • mark the bike as used
  • increment assigned count

Because pairs are processed in priority order, the first valid assignment is always correct.

Step 5: Stop Early

Once every worker has been assigned, terminate the loop and return the result.

This avoids unnecessary processing of remaining pairs.

Why it Works

The algorithm works because sorting all pairs globally reproduces the exact selection order required by the problem.

At any point in the process, the next valid pair in sorted order is precisely the pair the problem statement would choose:

  • minimum distance
  • then minimum worker index
  • then minimum bike index

Since assignments are only made when both the worker and bike remain available, the simulation exactly matches the required greedy process.

Python Solution

from typing import List

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
        pairs = []

        # Generate all worker-bike pairs
        for worker_index, (wx, wy) in enumerate(workers):
            for bike_index, (bx, by) in enumerate(bikes):
                distance = abs(wx - bx) + abs(wy - by)
                pairs.append((distance, worker_index, bike_index))

        # Sort by:
        # 1. distance
        # 2. worker index
        # 3. bike index
        pairs.sort()

        result = [-1] * len(workers)
        used_bikes = set()
        assigned_workers = 0

        # Process pairs in priority order
        for _, worker_index, bike_index in pairs:
            if result[worker_index] != -1:
                continue

            if bike_index in used_bikes:
                continue

            result[worker_index] = bike_index
            used_bikes.add(bike_index)
            assigned_workers += 1

            if assigned_workers == len(workers):
                break

        return result

The implementation begins by generating every possible worker-bike pair. For each pair, the Manhattan distance is computed and stored alongside the worker and bike indices.

The pairs.sort() call is especially important. Python sorts tuples lexicographically, so tuples of the form:

(distance, worker_index, bike_index)

automatically follow the required tie breaking rules.

The result array tracks which bike each worker receives. Initially, every value is -1, meaning unassigned.

The used_bikes set ensures that no bike is assigned more than once.

The main processing loop iterates through the sorted pairs. If either the worker already has a bike or the bike has already been used, the pair is skipped. Otherwise, the assignment is performed immediately.

The loop stops once all workers have been assigned, which avoids unnecessary extra work.

Go Solution

package main

import "sort"

func assignBikes(workers [][]int, bikes [][]int) []int {
	type Pair struct {
		distance int
		worker   int
		bike     int
	}

	pairs := []Pair{}

	// Generate all worker-bike pairs
	for wi, worker := range workers {
		for bi, bike := range bikes {
			distance := abs(worker[0]-bike[0]) + abs(worker[1]-bike[1])

			pairs = append(pairs, Pair{
				distance: distance,
				worker:   wi,
				bike:     bi,
			})
		}
	}

	// Sort according to problem rules
	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i].distance != pairs[j].distance {
			return pairs[i].distance < pairs[j].distance
		}

		if pairs[i].worker != pairs[j].worker {
			return pairs[i].worker < pairs[j].worker
		}

		return pairs[i].bike < pairs[j].bike
	})

	result := make([]int, len(workers))
	for i := range result {
		result[i] = -1
	}

	usedBikes := make([]bool, len(bikes))
	assignedWorkers := 0

	// Process pairs in sorted order
	for _, pair := range pairs {
		if result[pair.worker] != -1 {
			continue
		}

		if usedBikes[pair.bike] {
			continue
		}

		result[pair.worker] = pair.bike
		usedBikes[pair.bike] = true
		assignedWorkers++

		if assignedWorkers == len(workers) {
			break
		}
	}

	return result
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go solution follows the same overall structure as the Python implementation, but there are a few language specific differences.

Go does not have built in tuple sorting like Python, so we define a Pair struct containing the distance, worker index, and bike index.

Sorting is performed with sort.Slice, using a custom comparator that explicitly implements the tie breaking rules.

Instead of using a set for bike tracking, the Go solution uses a boolean slice. Since bike indices range from 0 to m - 1, direct indexing is efficient and simple.

The result slice is initialized with -1 values so we can distinguish assigned workers from unassigned workers.

Integer overflow is not a concern here because coordinate values are small and Manhattan distances remain well within Go's integer range.

Worked Examples

Example 1

workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]

Step 1: Generate All Pairs

Worker Bike Distance
0 0 3
0 1 6
1 0 2
1 1 3

Step 2: Sort Pairs

Order Pair
1 (2, 1, 0)
2 (3, 0, 0)
3 (3, 1, 1)
4 (6, 0, 1)

Step 3: Process Assignments

Current Pair Worker Assigned? Bike Used? Action Result
(2,1,0) No No Assign [-1, 0]
(3,0,0) No Yes Skip [-1, 0]
(3,1,1) Yes No Skip [-1, 0]
(6,0,1) No No Assign [1, 0]

Final answer:

[1, 0]

Example 2

workers = [[0,0],[1,1],[2,0]]
bikes = [[1,0],[2,2],[2,1]]

Step 1: Generate Distances

Worker Bike Distance
0 0 1
0 1 4
0 2 3
1 0 1
1 1 2
1 2 1
2 0 1
2 1 2
2 2 1

Step 2: Sort Pairs

The important early pairs become:

Order Pair
1 (1,0,0)
2 (1,1,0)
3 (1,1,2)
4 (1,2,0)
5 (1,2,2)

Step 3: Process Assignments

Current Pair Action Result
(1,0,0) Assign bike 0 to worker 0 [0, -1, -1]
(1,1,0) Bike already used [0, -1, -1]
(1,1,2) Assign bike 2 to worker 1 [0, 2, -1]
(1,2,0) Bike already used [0, 2, -1]
(1,2,2) Bike already used [0, 2, -1]

The next valid pair assigns bike 1 to worker 2.

Final result:

[0, 2, 1]

Complexity Analysis

Measure Complexity Explanation
Time O(n × m log(n × m)) Sorting all worker-bike pairs dominates the runtime
Space O(n × m) All pairs are stored before sorting

The algorithm generates every possible worker-bike pair exactly once, which requires n × m entries.

Sorting these pairs costs:

$$O((n \times m)\log(n \times m))$$

The assignment pass afterward is linear in the number of pairs and does not change the overall complexity.

The memory usage is dominated by storing all pairs before sorting.

Test Cases

sol = Solution()

# Example 1
assert sol.assignBikes(
    [[0, 0], [2, 1]],
    [[1, 2], [3, 3]]
) == [1, 0]

# Example 2
assert sol.assignBikes(
    [[0, 0], [1, 1], [2, 0]],
    [[1, 0], [2, 2], [2, 1]]
) == [0, 2, 1]

# Single worker and single bike
assert sol.assignBikes(
    [[0, 0]],
    [[1, 1]]
) == [0]

# Tie on distance, smaller worker index wins
assert sol.assignBikes(
    [[0, 0], [2, 0]],
    [[1, 0], [3, 0]]
) == [0, 1]

# Tie on distance and worker, smaller bike index wins
assert sol.assignBikes(
    [[0, 0]],
    [[1, 0], [0, 1]]
) == [0]

# More bikes than workers
assert sol.assignBikes(
    [[0, 0], [10, 10]],
    [[1, 1], [9, 9], [20, 20]]
) == [0, 1]

# Workers competing for same bike
assert sol.assignBikes(
    [[0, 0], [1, 0]],
    [[0, 1], [10, 10]]
) == [0, 1]

# Large coordinate values
assert sol.assignBikes(
    [[999, 999]],
    [[0, 0], [998, 999]]
) == [1]

# Multiple equal distances
assert sol.assignBikes(
    [[0, 0], [1, 1]],
    [[1, 0], [0, 1]]
) == [0, 1]

Test Summary

Test Why
Example 1 Validates standard assignment flow
Example 2 Validates tie breaking rules
Single worker and bike Smallest valid input
Worker index tie breaking Confirms smaller worker index priority
Bike index tie breaking Confirms smaller bike index priority
More bikes than workers Ensures unused bikes are handled correctly
Competing workers Ensures bikes cannot be reused
Large coordinates Confirms Manhattan distance computation
Multiple equal distances Stress tests deterministic ordering

Edge Cases

One important edge case occurs when many worker-bike pairs share the same Manhattan distance. This can easily produce incorrect results if sorting does not strictly follow all tie breaking rules. The implementation handles this by storing tuples or structs ordered as (distance, workerIndex, bikeIndex), ensuring deterministic ordering.

Another important case happens when multiple workers compete for the same bike. A naive implementation might accidentally assign the same bike multiple times if assignment state is not tracked carefully. The solution prevents this by maintaining a used_bikes structure and skipping already assigned bikes immediately.

A third edge case involves workers or bikes positioned very far apart. Large coordinate values can expose incorrect distance calculations or overflow issues in some languages. Since Manhattan distance uses only addition and subtraction of values below 1000, both Python and Go handle these computations safely without overflow concerns.

A final subtle edge case occurs when a worker's closest bike becomes unavailable because another worker claimed it earlier. The algorithm correctly handles this because assignments are made globally in sorted order rather than independently per worker. This guarantees that every assignment matches the exact greedy process described in the problem statement.