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 < nThis approach involves generating all subsets of requests and checking if they result in a balanced transfer of employees among all buildings. We maximize the number of requests in the subset where the number of inputs equals the number of outputs for every building.
This implementation uses backtracking. We use an indegree array to track the net transfer requests at each building. We consider each request to either choose or not choose a request while backtracking. We update maximum requests when all buildings are balanced at zero net requests.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^R * N), where R is the number of requests and N is the number of buildings.
Space Complexity: O(N), mainly because of the indegree array used for tracking the net inflow for each building.
This approach uses dynamic programming with bitmasking, reducing redundant calculations by storing results of previously computed states. It leverages the idea of subsets, where we test combinations represented as binary masks and check balance conditions for employee transfers.
The C solution uses a bitmask dynamic programming approach. It stores intermediate results of various combinations of requests in a dp array. The mask iterates over possible subsets of requests, updating indegree array and maximizing valid request count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^R * R * N) where R is the number of requests and N is the number of buildings.
Space Complexity: O(2^R) for dp array holding states by subsets of requests.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^R * N), where R is the number of requests and N is the number of buildings. Space Complexity: O(N), mainly because of the indegree array used for tracking the net inflow for each building. |
| Bitmask DP Approach | Time Complexity: O(2^R * R * N) where R is the number of requests and N is the number of buildings. Space Complexity: O(2^R) for dp array holding states by subsets of requests. |
Maximum Number of Achievable Transfer Requests | Khandani Backtracking Template | Leetcode-1601 • codestorywithMIK • 6,317 views views
Watch 9 more video solutions →Practice Maximum Number of Achievable Transfer Requests with our built-in code editor and test cases.
Practice on FleetCode