1601. Maximum Number of Achievable Transfer Requests LeetCode Solution
In this guide, you will get 1601. Maximum Number of Achievable Transfer Requests LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Achievable Transfer Requests problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Achievable Transfer Requests
We have n buildings numbered from 0 to n – 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.
You are given an array requests where requests[i] = [fromi, toi] represents an employee’s request to transfer from building fromi to building toi.
All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.
Return the maximum number of achievable requests.
Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explantion: Let’s see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don’t have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.
Example 2:
Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Explantion: Let’s see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests.
Example 3:
Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4
Constraints:
1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= fromi, toi < n
Complexity Analysis
Time Complexity: O(n \cdot 2^{|\texttt{requests}|})
Space Complexity: O(n + |\texttt{requests}|)
1601. Maximum Number of Achievable Transfer Requests LeetCode Solution in C++
class Solution {
public:
int maximumRequests(int n, vector<vector<int>>& requests) {
int ans = 0;
vector<int> degrees(n); // degrees[i] := degrees of the i-th building
function<void(int, int)> dfs = [&](int i, int processedReqs) {
if (i == requests.size()) {
if (ranges::all_of(degrees, [](int d) { return d == 0; }))
ans = max(ans, processedReqs);
return;
}
// Skip the requests[i].
dfs(i + 1, processedReqs);
// Process the requests[i].
--degrees[requests[i][0]];
++degrees[requests[i][1]];
dfs(i + 1, processedReqs + 1);
--degrees[requests[i][1]];
++degrees[requests[i][0]];
};
dfs(0, 0);
return ans;
}
}; /* code provided by PROGIEZ */
1601. Maximum Number of Achievable Transfer Requests LeetCode Solution in Java
class Solution {
public int maximumRequests(int n, int[][] requests) {
dfs(0, 0, requests, new int[n]);
return ans;
}
private int ans = 0;
private void dfs(int i, int processedReqs, int[][] requests, int[] degrees) {
if (i == requests.length) {
if (Arrays.stream(degrees).allMatch(d -> d == 0))
ans = Math.max(ans, processedReqs);
return;
}
// Skip the requests[i].
dfs(i + 1, processedReqs, requests, degrees);
// Process the requests[i].
--degrees[requests[i][0]];
++degrees[requests[i][1]];
dfs(i + 1, processedReqs + 1, requests, degrees);
--degrees[requests[i][1]];
++degrees[requests[i][0]];
}
} // code provided by PROGIEZ
1601. Maximum Number of Achievable Transfer Requests LeetCode Solution in Python
