Problem Explanation

We are given a scenario where we have to assign a unique bike to each person living on a 2D grid campus. The campus, workers and the bikes, all are represented on a 2D grid where each cell represents a distinct location.

The bikes and workers are paired according to the Manhattan distance between them (which is defined as |x1 - x2| + |y1 - y2|), and the pair with shortest Manhattan distance is assigned first. If more than one pair have the same shortest distance, then the pair with smallest worker index is chosen. If there are multiple ways to do this too, the pair with smallest bike index is chosen.

Our task is to determine the assignment of bikes to workers in such way that it fulfills all the conditions mentioned above.

For example, consider a grid with 2 workers and 2 bikes at following locations:

Workers: (0,0), (2,1)

Bikes: (1,2), (3,3)

For this instance, Worker 1 picks bike 0 as the manhattan distance between them is the shortest, then worker 0 is assigned bike 1 due to the given conditions. Hence, the output is [1,0] indicating worker at index 0 has bike at index 1 and worker at index 1 has bike at index 0.

Solution Approach

The solution uses the bucket sort algorithm where each worker-bike pair is placed into basis their manhattan distance. Then, for each bucket from short to large distance, we assign bikes to the workers if possible, i.e. the bike is not taken by someone else and the worker has not been assigned a bike already.

Python Solution

1
2python
3class Solution:
4    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
5        def manhattan(worker, bike):
6            return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
7        
8        distances = []
9        for i, worker in enumerate(workers):
10            for j, bike in enumerate(bikes):
11                distance = manhattan(worker, bike)
12                # add distance, worker index and bike index into distances list
13                distances.append((distance, i, j))
14        # sort the distances
15        distances.sort()
16        
17        result = [-1]*len(workers)
18        bike_taken = [False]*len(bikes)
19        
20        for _, worker, bike in distances:
21            if result[worker] == -1 and not bike_taken[bike]:
22                result[worker] = bike
23                bike_taken[bike] = True
24                
25        return result

Java Solution

1
2java
3class Solution {
4    public int[] assignBikes(int[][] workers, int[][] bikes) {
5        // bucket sort all the pairs by their distance
6        ArrayList<int[]>[] bucket = new ArrayList[2001];
7        int N = workers.length;
8        int M = bikes.length;
9        int[] res = new int[N];
10        boolean[] used = new boolean[M];
11        Arrays.fill(res, -1);
12
13        for (int i = 0; i < N; i++)
14            for (int j = 0; j < M; j++) {
15                int dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
16                if (bucket[dist] == null) {
17                    bucket[dist] = new ArrayList<int[]>();
18                }
19                bucket[dist].add(new int[]{i, j});
20            }
21
22        for (int i = 0; i <= 2000; i++) {
23            if (bucket[i] != null)
24                for (int j = 0; j < bucket[i].size(); j++) {
25                    int wo = bucket[i].get(j)[0];
26                    int bi = bucket[i].get(j)[1];
27                    if (res[wo] == -1 && !used[bi]) {
28                        res[wo] = bi;
29                        used[bi] = true;
30                    }
31                }
32        }
33        return res;
34    }
35}

JavaScript Solution

1
2javascript
3var assignBikes = function(workers, bikes) {
4    let q = [];
5    for (let i = 0; i < workers.length; i++) {
6        for (let j = 0; j < bikes.length; j++) {
7            let d = Math.abs(workers[i][0] - bikes[j][0]) + 
8                    Math.abs(workers[i][1] - bikes[j][1]);
9            q.push([d, i, j]);
10        }
11    }
12    q.sort((a, b) => a[0] - b[0] || 
13                      a[1] - b[1] || 
14                      a[2] - b[2]);
15
16    let res = new Array(workers.length).fill(-1), 
17        used = new Array(bikes.length).fill(false);
18    for (let [d, w, b] of q) {
19        if (res[w] === -1 && !used[b]) {
20            res[w] = b;
21            used[b] = true;
22        }
23    }
24    return res;
25};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
6        int n = workers.size(), m = bikes.size();
7        vector<vector<pair<int, int>>> dist(2001);
8        vector<int> res(n, -1);
9        vector<bool> used(m, false);
10        for (int i = 0; i < n; ++i) {
11            for (int j = 0; j < m; ++j) {
12                int d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
13                dist[d].push_back({i, j});
14            }
15        }
16        for (int i = 0; i <= 2000; ++i) { // iterate distances
17            for (auto& [w, b] : dist[i])    // iterate worker and matched bike pairs
18                if (res[w] < 0 and not used[b]) {
19                    used[b] = true;
20                    res[w] = b;
21                }
22        }
23        return res;
24    }
25};    

C# Solution

1
2csharp
3public class Solution {
4    public int[] AssignBikes(int[][] workers, int[][] bikes) {
5       var buckets = new List<(int worker, int bike)>[2001];
6       var workerBike = new int[workers.Length];
7       var usedBikes = new bool[bikes.Length];
8       for (var i = 0; i < workers.Length; i++){
9            for (var j = 0; j < bikes.Length; j++){
10                var w = workers[i];
11                var b = bikes[j];
12                var d = Math.Abs(w[0] - b[0]) + Math.Abs(w[1] - b[1]);
13                if (buckets[d] == null)
14                    buckets[d] = new List<(int worker, int bike)>();
15                buckets[d].Add((i, j));
16            }
17        }      
18        for (var d = 0; d < 2001; d++){
19            if (buckets[d] == null)
20                continue;
21            foreach(var d in buckets[d]){
22                var i = p.worker;
23                var j = p.bike;
24                if (workerBike[i] != 0 || usedBikes[j])
25                    continue;
26                workerBike[i] = j + 1;
27                usedBikes[j] = true;
28            }
29        }
30        return workerBike.Select(b => b - 1).ToArray();
31    }
32}

Note: The function that needs to be implemented will vary based on the language.

• Python uses snake_case for function names.
• Java, C# uses PascalCase for class and method names.
• JavaScript uses camelCase for function names.
• C++ uses camelCase for method names and PascalCase for class names.Each solution uses a similar approach, but there are some differences in the implementation due to language-specific intricacies.

For instance, Python and JavaScript solutions initialize a list with distances, workers and bikes indexes. Then, they perform a sort operation and iterate through the sorted list to assign bikes to workers.

The Java solution uses a slightly different approach. It uses a bucket sort algorithm to sort the distances, then makes the bike assignment.

The C++ and C# solution uses a vector of pairs where each pair contains a worker index and a bike index. It uses a bucket sort strategy similar to the Java solution for sorting and assigning bikes to workers.

Some general tips:

1. Understand the problem. Then, create a pseudocode or flow diagram to solve the problem step by step.

2. Understand the strengths and weaknesses of your programming language to use the most efficient data structures and algorithms.

3. Write the code and test it with several test cases, especially edge cases to ensure it works correctly.

4. Comment your code well to explain what each key section is doing.

5. Keep practicing with different problems in the field, and over time, you will improve your algorithmic thinking and coding skills.

As seen above, most solutions to programming algorithm problems can generally be implemented in various languages, once the logic is understood. The key to solving such problems is understanding how they can be broken down logically, and how these pieces can then be translated into code.