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 < nThe key observation in #1601 Maximum Number of Achievable Transfer Requests is that a set of transfer requests is valid only if the net change of employees for every building is zero. Each request moves one employee from building from to building to, so we must ensure the inflow and outflow balance for every building.
A common strategy is to enumerate all possible subsets of requests. For each subset, maintain an array representing the net employee change per building. When processing a request, decrement the source building and increment the destination building. After evaluating the subset, check whether all values are zero. If so, update the maximum number of achievable requests.
This can be implemented using bit manipulation to iterate through all 2^m subsets or through backtracking that explores including or excluding each request while tracking building balances. Since the number of requests is small, this exhaustive search is feasible. The goal is to maximize the subset size while maintaining balanced transfers.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Enumeration of Requests | O(2^m * m) | O(n) |
| Backtracking with Balance Tracking | O(2^m) | O(n) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Think brute force
When is a subset of requests okay?
This 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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int max_requests;
6
7void
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The number of transfer requests is relatively small, making it feasible to check all possible combinations. By evaluating each subset and validating building balances, we can guarantee finding the maximum achievable set of requests.
Yes, problems involving subset enumeration, backtracking, and balance tracking are common in FAANG-style interviews. This problem tests reasoning about constraints, optimization, and efficient exploration of combinations.
An integer array is typically used to track the net employee change for each building. This array helps verify whether the inflow and outflow of employees balance out after processing a subset of requests.
The optimal approach is to enumerate all subsets of requests using bit manipulation or backtracking. For each subset, track the net employee balance for every building and ensure all balances return to zero. The subset with the maximum valid requests is the answer.
The Python solution explores each potential set subset using a bitmask. The indegree is summed for each subset, checking balance, and updating the maximum achievable number of requests accordingly.