1057. Campus Bikes
Problem Description
The task involves assigning bikes to workers on a campus that is laid out on an X-Y coordinate plane. There are n
workers and m
bikes, with the condition that n <= m
, meaning there are at least as many bikes as there are workers. Each worker and bike has a unique position on the plane, represented by their coordinates.
The goal is to assign each worker exactly one bike based on the shortest Manhattan distance between them. The Manhattan distance between two points p1
and p2
is defined as |p1.x - p2.x| + |p1.y - p2.y|
, which essentially measures the distance between the points if you could only move along the grid horizontally or vertically.
If multiple workers could be assigned to the same bike due to equal distances, the worker with the lower index gets priority. Similarly, if one worker has the option of multiple bikes at the same distance, the bike with the lower index is assigned.
The output should be an array where each element represents the index of the bike assigned to the worker at the corresponding index.
Intuition
The solution approach requires creating a list of all possible combinations of workers and bikes along with their Manhattan distances. These combinations are then sorted primarily by the distance, then by the worker index, and finally by the bike index. This guarantees that the shortest and prioritized combinations (based on worker and bike indices) are considered first in the sorted list.
Once sorted, the algorithm iterates through the list of combinations and assigns bikes to workers one by one. During this process, both workers and bikes are marked as 'visited' to ensure that each worker gets only one bike, and each bike is assigned only once.
By sorting the combination of distances and applying the rules of priority in indexing, we ensure an efficient distribution of bikes to workers based on the proximity and predefined rules. This approach guarantees that the problem constraints will be respected and the correct assignments will be made.
Solution Approach
The reference solution provided implements a straightforward but effective algorithm to solve the problem with a greedy approach. Here is a walkthrough of the solution step by step:
-
Collect Pair Information: Initially, the solution collects all possible combinations of worker and bike pairs along with their Manhattan distances. This is done using a nested loop to iterate over each worker and bike to calculate their distance:
dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
. -
Distance-Pair Array: These pairs, along with the distances, are stored in an array where each element is a tuple comprising the distance, the worker index
i
, and the bike indexj
:(dist, i, j)
. -
Sorting Pair Array: Next, the tuples are sorted based on the first, second, and third elements (distance, worker index, and bike index, respectively). This orders the pairings primarily by the shortest distance, then by the smallest worker index, and lastly by the smallest bike index if there's a tie on the distance.
-
Initialize Visited Flags: Two arrays
vis1
for workers andvis2
for bikes are created to keep track of whether a worker has been assigned a bike and whether a bike has been taken by a worker. -
Assignment: The solution iterates through the sorted array and checks the visited flags for both workers and bikes. If both are unvisited, (i.e., the worker has not yet been assigned a bike and the bike has not been assigned to any worker), the bike is assigned to the worker:
ans[i] = j
and the visited flags are updated toTrue
. -
Return Assignment: Once all workers have been assigned a bike, the
ans
array, which holds the mapping of workers to their assigned bike indices, is returned.
It is worth noting that this approach leverages the Python's tuple sorting behavior which automatically sorts the tuples based on their first element, and in case of ties, it uses the second element, and so on. The algorithm also makes efficient use of space by using boolean arrays to keep track of the workers and bikes that have already been assigned. This algorithm achieves a balance between performance and clarity, allowing for an effective solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach with 2 workers and 3 bikes.
Initial Setup:
- Workers' coordinates:
[(0, 0), (2, 1)]
(Worker 0 at(0, 0)
and Worker 1 at(2, 1)
) - Bikes' coordinates:
[(1, 0), (2, 2), (2, 3)]
(Bike 0 at(1, 0)
, Bike 1 at(2, 2)
, and Bike 2 at(2, 3)
)
Step 1: Collect Pair Information We begin by calculating the Manhattan distance for all possible worker-bike pairs:
- Worker 0 & Bike 0:
abs(0 - 1) + abs(0 - 0) = 1
- Worker 0 & Bike 1:
abs(0 - 2) + abs(0 - 2) = 4
- Worker 0 & Bike 2:
abs(0 - 2) + abs(0 - 3) = 5
- Worker 1 & Bike 0:
abs(2 - 1) + abs(1 - 0) = 2
- Worker 1 & Bike 1:
abs(2 - 2) + abs(1 - 2) = 1
- Worker 1 & Bike 2:
abs(2 - 2) + abs(1 - 3) = 2
Step 2: Distance-Pair Array Construct an array with the pairs and their distances:
[(1, 0, 0), (4, 0, 1), (5, 0, 2), (2, 1, 0), (1, 1, 1), (2, 1, 2)]
Step 3: Sorting Pair Array Sort the array of tuples by distance, then by worker index, and then by bike index:
[(1, 0, 0), (1, 1, 1), (2, 1, 0), (2, 1, 2), (4, 0, 1), (5, 0, 2)]
Step 4: Initialize Visited Flags Create boolean arrays to track the visited workers and bikes:
vis1 = [False, False]
(for workers)vis2 = [False, False, False]
(for bikes)
Step 5: Assignment Iterate through the sorted pairs and assign bikes to workers:
- Worker 0 is assigned Bike 0 because the pair
(1, 0, 0)
comes first and both Worker 0 and Bike 0 are unvisited. Mark Worker 0 and Bike 0 as visited. - Skip to the next unvisited pair
(1, 1, 1)
. Assign Worker 1 to Bike 1 and mark them as visited. - Remaining pairs either contain a worker or a bike that has already been assigned, so we skip them.
Step 6: Return Assignment
The ans
array after the assignments is [0, 1]
, indicating that Worker 0 is assigned Bike 0 and Worker 1 is assigned Bike 1.
Now the assignment mapping of workers to bike indices is returned, completing the algorithm execution for the given example.
Solution Implementation
1from typing import List
2from itertools import product
3
4class Solution:
5 def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
6 num_workers = len(workers)
7 num_bikes = len(bikes)
8 distances = [] # List to hold the distance and associated worker and bike indices
9
10 # Calculate the manhattan distances between each worker-bike pair and store them
11 for worker_index, bike_index in product(range(num_workers), range(num_bikes)):
12 distance = abs(workers[worker_index][0] - bikes[bike_index][0]) \
13 + abs(workers[worker_index][1] - bikes[bike_index][1])
14 distances.append((distance, worker_index, bike_index))
15
16 # Sort the distances list in ascending order
17 distances.sort()
18
19 # Initialize the visited lists for workers and bikes
20 visited_workers = [False] * num_workers
21 visited_bikes = [False] * num_bikes
22 assignments = [-1] * num_workers # -1 to indicate unassigned workers
23
24 # Assign bikes to workers based on sorted distances
25 for distance, worker_index, bike_index in distances:
26 # Assign a bike to a worker if both are unvisited/unassigned
27 if not visited_workers[worker_index] and not visited_bikes[bike_index]:
28 visited_workers[worker_index] = True # Mark the worker as visited
29 visited_bikes[bike_index] = True # Mark the bike as visited
30 assignments[worker_index] = bike_index # Assign the bike to the worker
31
32 return assignments
33
1class Solution {
2 public int[] assignBikes(int[][] workers, int[][] bikes) {
3 int numWorkers = workers.length;
4 int numBikes = bikes.length;
5 // Create an array to store distance, worker index, and bike index
6 int[][] distances = new int[numWorkers * numBikes][3];
7
8 // Calculate the Manhattan distance between each worker and bike pair
9 int index = 0;
10 for (int i = 0; i < numWorkers; ++i) {
11 for (int j = 0; j < numBikes; ++j) {
12 int dist = Math.abs(workers[i][0] - bikes[j][0]) +
13 Math.abs(workers[i][1] - bikes[j][1]);
14 distances[index++] = new int[] {dist, i, j};
15 }
16 }
17
18 // Sort the distances array by distance first, then worker index, then bike index
19 Arrays.sort(distances, (a, b) -> {
20 if (a[0] != b[0]) {
21 return a[0] - b[0]; // Compare distances
22 }
23 if (a[1] != b[1]) {
24 return a[1] - b[1]; // Compare worker indices
25 }
26 return a[2] - b[2]; // Compare bike indices
27 });
28
29 // Keep track of which workers and bikes have been visited/assigned
30 boolean[] workersVisited = new boolean[numWorkers];
31 boolean[] bikesVisited = new boolean[numBikes];
32 int[] assignments = new int[numWorkers]; // Result array with assignments
33
34 // Assign bikes to workers based on the sorted distances
35 for (int[] arr : distances) {
36 int workerIdx = arr[1];
37 int bikeIdx = arr[2];
38 // If the current worker and bike have not been visited yet, assign the bike to the worker
39 if (!workersVisited[workerIdx] && !bikesVisited[bikeIdx]) {
40 workersVisited[workerIdx] = true;
41 bikesVisited[bikeIdx] = true;
42 assignments[workerIdx] = bikeIdx;
43 }
44 }
45
46 return assignments; // Return the final assignment of bikes to workers
47 }
48}
49
1#include <vector>
2#include <tuple>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 // Function to assign bikes to workers
9 vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
10 int numWorkers = workers.size();
11 int numBikes = bikes.size();
12
13 // Create an array to store the distances and indices
14 vector<tuple<int, int, int>> allPairs(numWorkers * numBikes);
15
16 // Iterate over each worker and each bike to calculate distances
17 for (int workerIndex = 0, pairIndex = 0; workerIndex < numWorkers; ++workerIndex) {
18 for (int bikeIndex = 0; bikeIndex < numBikes; ++bikeIndex) {
19 int distance = abs(workers[workerIndex][0] - bikes[bikeIndex][0]) +
20 abs(workers[workerIndex][1] - bikes[bikeIndex][1]);
21 // Store the tuple of distance, worker index, and bike index
22 allPairs[pairIndex++] = {distance, workerIndex, bikeIndex};
23 }
24 }
25
26 // Sort all pairs by distance, then by worker index, then by bike index
27 sort(allPairs.begin(), allPairs.end());
28
29 // Vectors to keep track of which workers and bikes have been visited
30 vector<bool> workerVisited(numWorkers, false);
31 vector<bool> bikeVisited(numBikes, false);
32
33 // Initialize the answer vector to store the bike index for each worker
34 vector<int> answer(numWorkers, -1); // Default to -1 for unassigned
35
36 // Iterate over each sorted pair
37 for (auto& [distance, workerIndex, bikeIndex] : allPairs) {
38 // If the current worker and bike have not been visited
39 if (!workerVisited[workerIndex] && !bikeVisited[bikeIndex]) {
40 // Assign the bike to the worker
41 workerVisited[workerIndex] = true;
42 bikeVisited[bikeIndex] = true;
43 answer[workerIndex] = bikeIndex;
44 }
45 }
46
47 // Return the final assignment of bikes to workers
48 return answer;
49 }
50};
51
1// Import necessary elements from array functions
2import { abs, sort } from 'math';
3
4// Type definition for a pair representing distance, worker index, and bike index
5type WorkerBikePair = [number, number, number];
6
7// Function to calculate the Manhattan distance between a worker and a bike
8function calculateManhattanDistance(worker: number[], bike: number[]): number {
9 return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1]);
10}
11
12// Function to assign bikes to workers based on their Manhattan distances
13function assignBikes(workers: number[][], bikes: number[][]): number[] {
14 const numWorkers: number = workers.length;
15 const numBikes: number = bikes.length;
16
17 // Array to store all worker-bike pairs with their corresponding distances
18 const allPairs: WorkerBikePair[] = [];
19
20 // Populate the array with distances and indices
21 for (let workerIndex = 0; workerIndex < numWorkers; ++workerIndex) {
22 for (let bikeIndex = 0; bikeIndex < numBikes; ++bikeIndex) {
23 const distance: number = calculateManhattanDistance(workers[workerIndex], bikes[bikeIndex]);
24 allPairs.push([distance, workerIndex, bikeIndex]);
25 }
26 }
27
28 // Sort the pairs by distance, then by worker index, then by bike index
29 allPairs.sort((a, b) => {
30 // Compare by distance
31 if (a[0] !== b[0]) {
32 return a[0] - b[0];
33 }
34 // If distance is the same, compare by worker index
35 if (a[1] !== b[1]) {
36 return a[1] - b[1];
37 }
38 // If distance and worker index are the same, compare by bike index
39 return a[2] - b[2];
40 });
41
42 // Arrays to keep track of whether workers or bikes are already matched
43 const workerVisited: boolean[] = new Array(numWorkers).fill(false);
44 const bikeVisited: boolean[] = new Array(numBikes).fill(false);
45
46 // Array to keep the results of bike assignments for each worker
47 const answer: number[] = new Array(numWorkers).fill(-1);
48
49 // Assign bikes to workers based on the sorted allPairs
50 for (const [distance, workerIndex, bikeIndex] of allPairs) {
51 // Proceed if both the worker and the bike are not yet visited
52 if (!workerVisited[workerIndex] && !bikeVisited[bikeIndex]) {
53 // Mark as matched
54 workerVisited[workerIndex] = true;
55 bikeVisited[bikeIndex] = true;
56 // Assign the bike to the worker in the answer array
57 answer[workerIndex] = bikeIndex;
58 }
59 }
60
61 // Return the final assignments
62 return answer;
63}
64
Time and Space Complexity
The time complexity and space complexity of the given code can be analyzed as follows:
Time Complexity
-
The nested loop with
product(range(n), range(m))
generates all possible pairs of workers and bikes. There aren
workers andm
bikes, so there aren * m
pairs. This operation has a time complexity ofO(n * m)
. -
Calculating the Manhattan distance for each worker-bike pair takes constant time, so this does not change the overall time complexity from
O(n * m)
. -
Appending each tuple
(dist, i, j)
to thearr
list is donen * m
times, which is alsoO(n * m)
. -
The sort operation on
arr
has a time complexity ofO(n * m * log(n * m))
because sorting is typically implemented with anO(n log n)
complexity, and here we are sortingn * m
elements. -
The final loop goes over the sorted array, which has
n * m
elements, and it assigns bikes to workers. Since each worker and bike is visited at most once, the loop will run at mostn + m
times - because once every worker has a bike, the process stops. The time complexity for this loop is thusO(n + m)
.
Therefore, the overall time complexity of the code is dominated by the sorting step, which is O(n * m * log(n * m))
.
Space Complexity
-
The
arr
list containsn * m
tuples, so it has a space complexity ofO(n * m)
. -
The
vis1
andvis2
arrays each have a space complexity ofO(n)
andO(m)
respectively. Adding them together givesO(n + m)
. -
The answer array
ans
has a space complexity ofO(n)
because it must hold an assignment for each worker.
The additional space required is for the tuples and the arrays to track the visited workers and bikes. Since these do not depend on the size of the input apart from the number of workers and bikes, we can consider them all in aggregate.
Hence, the overall space complexity is O(n * m)
as it is the term that grows more significantly with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.