Maximum Number of Achievable Transfer Requests
HardPrompt
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.
Example 1:
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 <= 201 <= requests.length <= 16requests[i].length == 20 <= fromi, toi < n
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible subset of the given transfer requests. Since the number of requests is small (up to 16), we can represent each subset using a bitmask. For each subset, we check if it's "achievable" by calculating the net change in employees for each building. If the net change is zero for all buildings, the subset is valid, and we update our maximum count.
Algorithm
- Initialize
maxAchievable = 0. - Let
mbe the number of requests. - Loop through each integer
maskfrom0to2^m - 1. Eachmaskrepresents a subset of requests. - For each
mask:- Initialize a
balancearray of sizento all zeros. - Initialize
subsetSize = 0. - Iterate from
j = 0tom - 1:- If the
j-th bit is set inmask, it meansrequests[j]is in the subset. - Increment
subsetSize. - Update the
balanceforrequests[j]: decrementbalanceat thefromindex and increment at thetoindex.
- If the
- After processing all requests in the subset, check if all elements in the
balancearray are zero. - If the balance condition is met, update
maxAchievable = max(maxAchievable, subsetSize).
- Initialize a
- After checking all
2^mmasks, returnmaxAchievable.
Walkthrough
We iterate through all numbers from 0 to 2^m - 1, where m is the total number of requests. Each number i in this range acts as a bitmask, representing a unique subset of requests.
If the j-th bit in the mask i is set, it signifies that the j-th request is included in the current subset.
For each mask, we perform the following steps:
- Create a
balancearray of sizen(fornbuildings), initialized to all zeros. This array will track the net flow of employees for each building. - Count the number of requests in the current subset (which is the number of set bits in the mask).
- Iterate through the requests. For each request
[from, to]included in the subset, we decrementbalance[from]and incrementbalance[to]. - After processing all requests in the subset, we check if all entries in the
balancearray are zero. This condition means that for every building, the number of employees leaving equals the number of employees arriving. - If the balance condition is met, the subset is achievable. We then compare the size of this valid subset with our current maximum and update it if the current subset is larger.
After checking all 2^m subsets, the maximum value found is the answer.
class Solution { public int maximumRequests(int n, int[][] requests) { int m = requests.length; int maxAchievable = 0; for (int i = 0; i < (1 << m); i++) { int[] balance = new int[n]; int currentRequests = 0; // Check which requests are in the current subset represented by 'i' for (int j = 0; j < m; j++) { if ((i & (1 << j)) != 0) { int from = requests[j][0]; int to = requests[j][1]; balance[from]--; balance[to]++; currentRequests++; } } // Check if this subset is achievable boolean isAchievable = true; for (int k = 0; k < n; k++) { if (balance[k] != 0) { isAchievable = false; break; } } if (isAchievable) { maxAchievable = Math.max(maxAchievable, currentRequests); } } return maxAchievable; }}Complexity
Time
O(2^m * (m + n)), where `m` is the number of requests and `n` is the number of buildings. The outer loop runs `2^m` times. Inside, we iterate up to `m` times to build the balance array and `n` times to check it.
Space
O(n), where `n` is the number of buildings, required to store the `balance` array.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Directly translates the problem of checking all subsets into code.
Cons
Inefficient due to re-calculating the balance for each of the
2^msubsets from scratch.The time complexity is exponential, making it unsuitable for a larger number of requests.
This approach uses recursion (backtracking) to explore all possible subsets of requests. It is more efficient than the pure brute-force method because it builds the state (the balance of employees per building) incrementally. At each step of the recursion, we decide whether to include the current request or not. This avoids recalculating the balance for each subset from scratch and allows for potential optimizations like pruning the search space.
Algorithm
- Initialize a global
maxAchievable = 0and abalancearray of sizen. - Define a recursive function
backtrack(index, count, requests, balance). - Base Case: If
indexreachesrequests.length:- Check if all elements in the
balancearray are zero. - If they are, it's a valid configuration. Update
maxAchievable = max(maxAchievable, count). - Return.
- Check if all elements in the
- Recursive Step: At
requests[index], explore two choices:- 1. Exclude
requests[index]: Make a recursive callbacktrack(index + 1, count, ...). - 2. Include
requests[index]:- Update the
balancearray based on the current request. - Make a recursive call
backtrack(index + 1, count + 1, ...). - Crucially, revert the changes made to the
balancearray to backtrack for other recursive paths.
- Update the
- 1. Exclude
- Start the process by calling
backtrack(0, 0, requests, new int[n]). - Return
maxAchievable.
Walkthrough
We define a recursive helper function, backtrack(index, count), which explores subsets starting from requests[index]. The count parameter tracks the number of requests included in the current path. We use a balance array, passed through the recursion, to track the net change for each building.
The base case for the recursion is when index reaches the end of the requests array. At this point, we have a complete subset. We check if the balance array is all zeros. If it is, we've found an achievable combination of requests, and we update our global maximum with the current count.
In the recursive step for requests[index], we explore two possibilities:
- Exclude the request: We don't include the current request in our subset and simply move to the next one by calling
backtrack(index + 1, count). Thebalancearray remains unchanged. - Include the request: We tentatively add the current request to our subset. We update the
balancearray forrequests[index](decrementing for thefrombuilding, incrementing for thetobuilding) and then make a recursive callbacktrack(index + 1, count + 1).
After the recursive call for including the request returns, we must backtrack by reverting the changes made to the balance array. This is a critical step that ensures the balance array is in the correct state for other branches of the recursion.
The initial call to start the process is backtrack(0, 0) with a fresh balance array.
class Solution { int maxAchievable = 0; public int maximumRequests(int n, int[][] requests) { int[] balance = new int[n]; backtrack(0, 0, requests, balance); return maxAchievable; } private void backtrack(int index, int count, int[][] requests, int[] balance) { // Base case: we have processed all requests if (index == requests.length) { // Check if all buildings have a net change of 0 for (int b : balance) { if (b != 0) { return; // Not a valid state } } maxAchievable = Math.max(maxAchievable, count); return; } // --- Explore two choices for the current request --- // Choice 1: Exclude requests[index] backtrack(index + 1, count, requests, balance); // Choice 2: Include requests[index] int from = requests[index][0]; int to = requests[index][1]; balance[from]--; balance[to]++; backtrack(index + 1, count + 1, requests, balance); // Backtrack: undo the change for the next exploration path balance[from]++; balance[to]--; }}Complexity
Time
O(2^m * n). The recursion tree has `2^m` leaf nodes (representing all subsets). At each leaf, we perform an `O(n)` check on the balance array. The work at internal nodes is constant.
Space
O(m + n). `O(m)` for the recursion call stack depth and `O(n)` for the `balance` array.
Trade-offs
Pros
More efficient than the bitmasking approach as it avoids recalculating the balance from scratch for every subset.
The recursive structure is a natural fit for subset enumeration problems.
Can be easily optimized with pruning techniques to cut off search paths that won't lead to a better solution.
Cons
Still has an exponential time complexity, making it infeasible for a large number of requests (
m).Recursive solutions can sometimes be harder to debug and may lead to stack overflow for very deep recursion (not an issue with
m <= 16).
Solutions
Solution
public class Solution { private int m ; private int n ; private int [][] requests ; public int MaximumRequests ( int n , int [][] requests ) { m = requests . Length ; this . n = n ; this . requests = requests ; int ans = 0 ; for ( int mask = 0 ; mask < ( 1 << m ); ++ mask ) { int cnt = CountBits ( mask ); if ( ans < cnt && Check ( mask )) { ans = cnt ; } } return ans ; } private bool Check ( int mask ) { int [] cnt = new int [ n ]; for ( int i = 0 ; i < m ; ++ i ) { if ((( mask >> i ) & 1 ) == 1 ) { int f = requests [ i ][ 0 ], t = requests [ i ][ 1 ]; -- cnt [ f ]; ++ cnt [ t ]; } } foreach ( int v in cnt ) { if ( v != 0 ) { return false ; } } return true ; } private int CountBits ( int n ) { int count = 0 ; while ( n > 0 ) { n -= n & - n ; ++ count ; } return count ; } }class Solution {private int m;private int n;private int[][] requests;public int maximumRequests(int n, int[][] requests) { m = requests.length; this.n = n; this.requests = requests; int ans = 0; for (int mask = 0; mask < 1 << m; ++mask) { int cnt = Integer.bitCount(mask); if (ans < cnt && check(mask)) { ans = cnt; } } return ans; }private boolean check(int mask) { int[] cnt = new int[n]; for (int i = 0; i < m; ++i) { if ((mask >> i & 1) == 1) { int f = requests[i][0], t = requests[i][1]; --cnt[f]; ++cnt[t]; } } for (int v : cnt) { if (v != 0) { return false; } } return true; }}/** * @param {number} n * @param {number[][]} requests * @return {number} */ var maximumRequests = function (n, requests) { const m = requests.length; let ans = 0; const check = (mask) => { const cnt = new Array(n).fill(0); for (let i = 0; i < m; ++i) { if ((mask >> i) & 1) { const [f, t] = requests[i]; --cnt[f]; ++cnt[t]; } } return cnt.every((v) => v === 0); }; for (let mask = 0; mask < 1 << m; ++mask) { const cnt = bitCount(mask); if (ans < cnt && check(mask)) { ans = cnt; } } return ans; };function bitCount(i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f;}class Solution {public: int maximumRequests(int n, vector<vector<int>> &requests) { int m = requests.size(); int ans = 0; auto check = [&](int mask) -> bool { int cnt[n]; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < m; ++i) { if (mask >> i & 1) { int f = requests[i][0], t = requests[i][1]; --cnt[f]; ++cnt[t]; } } for (int v : cnt) { if (v) { return false; } } return true; }; for (int mask = 0; mask < 1 << m; ++mask) { int cnt = __builtin_popcount(mask); if (ans < cnt && check(mask)) { ans = cnt; } } return ans; }};class Solution: def maximumRequests(self, n: int, requests: List[List[int]]) -> int: def check(mask: int) -> bool: cnt = [0] * n for i, (f, t) in enumerate(requests): if mask >> i & 1: cnt[f] -= 1 cnt[t] += 1 return all(v == 0 for v in cnt) ans = 0 for mask in range(1 << len(requests)): cnt = mask . bit_count() if ans < cnt and check(mask): ans = cnt return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.