Watch 10 video solutions for Maximum Number of Achievable Transfer Requests, a hard level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by codestorywithMIK has 10,031 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 < nProblem Overview: You are given n buildings and a list of employee transfer requests where each request moves one employee from building from to building to. The goal is to accept the maximum number of requests such that the net change of employees in every building remains zero.
Approach 1: Backtracking with Balance Tracking (Time: O(2^m * n), Space: O(n))
Use backtracking to explore whether each request should be accepted or skipped. Maintain an array balance[n] where accepting a request decrements balance[from] and increments balance[to]. Recursively process all requests and track how many are chosen. When all requests are considered, verify that every building has zero balance; if so, update the maximum count. This approach prunes the search naturally and works well because the number of requests is small (≤20). It is intuitive for interviews and clearly demonstrates the constraint that every building must end balanced.
Approach 2: Bitmask Enumeration (Time: O(2^m * m), Space: O(n))
Enumerate all subsets of requests using bit manipulation. A bitmask from 0 to (1 << m) - 1 represents which requests are selected. For each mask, count the number of set bits and compute the building balance by iterating through the selected requests. If every building's balance is zero, the subset is valid and you update the answer with the maximum size. Iterating through subsets makes this a classic enumeration technique. Although it checks every subset, the constraint m ≤ 20 keeps the total manageable.
Recommended for interviews: The backtracking solution is usually expected because it models the decision process directly and allows pruning when the remaining requests cannot beat the current best. Bitmask enumeration is also acceptable and sometimes faster to implement, especially if you are comfortable with subset iteration using bit operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Balance Array | O(2^m * n) | O(n) | Best for interviews; easy to reason about and supports pruning while exploring request decisions |
| Bitmask Enumeration | O(2^m * m) | O(n) | Good when comfortable with subset iteration using bit operations; concise implementation |