Leetcode 1601. Maximum Number of Achievable Transfer Requests

Problem Explanation:

In this problem, a list of requests from employees wants to change the building they are currently residing in is given. The condition given is that every building should have net zero change in employees which means the number of employees leaving should be equal to the number of employees coming in. We are to find the maximum number of achievable requests.

For example, consider n=4 and request list is [[0,3],[3,1],[1,2],[2,0]]. It implies an employee wants to move from building 0 to 3, from building 3 to 1, from building 1 to 2 and from building 2 to 0. Here for each build, there is a single incoming and a single outgoing request, therefore providing net zero change for each building. As all requests can be achieved, output will be 4.

Solution Approach:

A depth-first search (DFS) approach is used to go through all possible combinations of taking or not taking a request. We can do this because the maximum size of requests is 16. For each combination, we then check if all the buildings have net 0 transfer of employees. If the condition is satisfied, we take maximum of the processed requests and the previous maximum.

Consider Example 1, we start with building 0 and check which buildings have sent request to it. As mentioned in the question the buildings are from 0 to n-1 so we start iterating from 0 and then check for the other buildings. This depth-first approach helps to trace back the requests and check all possible combinations to give the maximum number of achievable requests.

Python Solution:

1
2python
3from typing import List
4def maximumRequests(n: int, requests: List[List[int]]) -> int:
5    ans = 0
6    degree = [0]*n
7
8    def dfs(i, processedReqs):
9        nonlocal ans
10        if i == len(requests):
11            if all(d == 0 for d in degree):
12                ans = max(ans, processedReqs)
13            return
14
15        dfs(i + 1, processedReqs)
16        degree[requests[i][0]] -= 1
17        degree[requests[i][1]] += 1
18        dfs(i + 1, processedReqs + 1)
19        degree[requests[i][0]] += 1
20        degree[requests[i][1]] -= 1
21
22    dfs(0, 0)
23    return ans

Java Solution:

1
2java
3import java.util.*;
4class Solution {
5    public int maximumRequests(int n, int[][] requests) {
6        int m = requests.length, ans = 0;
7        int[] degree = new int[n];
8        for (int i = 0; i < 1 << m; i++) {
9            Arrays.fill(degree, 0);
10            for (int j = 0; j < m; j++) {
11                if ((i & (1 << j)) > 0) {
12                    degree[requests[j][0]]--;
13                    degree[requests[j][1]]++;
14                }
15            }
16            if (Arrays.stream(degree).allMatch(d -> d == 0))
17                ans = Math.max(ans, Integer.bitCount(i));
18        }
19
20        return ans;
21    }
22}

Javascript Solution:

1
2javascript
3var maximumRequests = function(n, requests) {
4    let res = 0;
5    const len = requests.length;
6    let num = Math.pow(2, len);
7
8    for (let i = 1; i < num; i++) {
9        let arr = Array(n).fill(0);
10        let bin = i.toString(2).padStart(len, '0');
11        let cnt = Array.from(bin).reduce((acc, cur, idx) => {
12            if (cur === '1') {
13                arr[requests[idx][0]]--;
14                arr[requests[idx][1]]++;
15                acc++;
16            }
17            return acc;
18        }, 0)
19        if (arr.every(c => c === 0)) {
20            res = Math.max(res, cnt);
21        }
22    }
23
24    return res;
25};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int maximumRequests(int n, vector<vector<int>>& requests) {
6        int m = requests.size(), ans = 0;
7        vector<int> degree(n, 0);
8        for (int state = 0; state < (1 << m); ++state) {
9            fill(degree.begin(), degree.end(), 0);
10            for (int i = 0; i < m; ++i) {
11                if (state & (1 << i)) {
12                    ++degree[requests[i][1]];
13                    --degree[requests[i][0]];
14                }
15            }
16            if (all_of(degree.begin(), degree.end(), [](int deg) {
17                return deg == 0;
18            })) {
19                ans = max(ans, __builtin_popcount(state));
20            }
21        }
22        return ans;
23    }
24};

C# Solution:

1
2csharp
3public class Solution {
4    public int MaximumRequests(int n, int[][] requests) {
5        int m = requests.Length, ans = 0;
6        int[] buildingMoves = new int[n];
7        for(int i = 0; i < 1 << m; i++){
8            Array.Fill(buildingMoves,0);
9            int cnt = 0;
10            for(int j = 0; j < m; j++){
11                if ((i & (1 << j)) > 0){
12                    buildingMoves[requests[j][0]] --;
13                    buildingMoves[requests[j][1]] ++;
14                    cnt ++;
15                }
16            }
17
18            if (buildingMoves.All(mv=> mv==0)){
19                ans = Math.Max(ans,cnt);
20            }
21        }
22        return ans;
23    }
24}

In all these solutions, initially ans is initialized to zero and the degree list/array represents the number of employees at each building. With DFS approach [Depth-First Search], the max number achievable requests are found by satisfying the condition where the number of employees leaving is equal to the number of employees moving in to maintain net zero. For Python, the depth list/array is used to store the net employee movement through each request. For other solutions, JavaScript, Java, C++ and C#, binary bitwise operations are utilized to track the count of employee's movements between buildings.

Golang Solution:

1
2go
3func maximumRequests(n int, requests [][]int) int {
4    rg, ans, m := make([]int, n), 0, len(requests)
5    for i := 0; i < 1 << m; i++ {
6        for j := 0; j < n; j++ {
7            rg[j] = 0
8        }
9        count := 0
10        for j := 0; j < m; j++ {
11            if i >> j & 1 == 1 {
12                rg[requests[j][0]]--
13                rg[requests[j][1]]++
14                count++
15            }
16        }
17        flag := true
18        for _, v := range rg {
19            if v != 0 {
20                flag = false
21                break
22            }
23        }
24        if flag {
25            ans = max(ans, count)
26        }
27    }
28    return ans
29}
30
31func max(a, b int) int {
32    if a > b {
33        return a
34    }
35    return b
36}

In the Golang solution, firstly, we need to create a list/array rg with size n to store the numbers of the employees in each building. We also define ans = 0, and m = length of requests. Then, we iterate i from 0 to 1 << m (left shift operator which implies the total number of possible combinations). For each i, we reset the list rg by setting all its elements to 0. We also define a variable count to store the number of valid movements. Then we iterate j from 0 to m to check if the ith bit of i is 1. If it is 1, we decrease the number of the employees in the start building and increase that in the end building, and add 1 to count. After that, we define a variable flag to check if all buildings have 0 movement. If all buildings have 0 movement, we update ans by the maximum value of ans and count. Finally, we just need to return ans as the result.

All the solutions provided uses the Depth-First Search algorithm at its core. This approach helps to ensure that there is zero net change of employees in any given building by comparing all possible combinations of employee movements. Finally the approach that yields the maximum number of requests is chosen as the correct solution. Regardless of the language used, the core logic of the solution remains the same.