1601. Maximum Number of Achievable Transfer Requests
Problem Description
You have n
buildings numbered from 0
to n - 1
, and each building has employees who want to transfer to different buildings during transfer season.
You're given an array requests
where each element requests[i] = [from_i, to_i]
represents an employee's request to move from building from_i
to building to_i
.
The key constraint is that all buildings are full. This means a set of transfer requests can only be approved if every building maintains the same number of employees after all transfers are complete. In other words, for each building, the number of employees leaving must equal the number of employees entering (net change = 0).
For example, if n = 3
:
- If 2 employees leave building 0, 1 leaves building 1, and 1 leaves building 2
- Then exactly 2 employees must enter building 0, 1 must enter building 1, and 1 must enter building 2
Your task is to find the maximum number of requests that can be fulfilled while maintaining this balance constraint for all buildings.
The solution uses binary enumeration to check all possible combinations of requests (since there are at most 16 requests). For each combination represented by a bitmask, it verifies if selecting those specific requests results in zero net change for every building. The answer is the largest valid combination found.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- No: While we have buildings and transfers between them, we're not solving a typical graph traversal or connectivity problem. We're selecting a subset of requests to fulfill.
Need to solve for kth smallest/largest?
- No: We're looking for the maximum number of achievable requests, not the kth smallest or largest element.
Involves Linked Lists?
- No: The problem involves arrays of transfer requests, not linked list data structures.
Does the problem have small constraints?
- Yes: The problem explicitly mentions that the length of requests does not exceed 16. This is a key indicator that we can enumerate all possible combinations (2^16 = 65,536 possibilities).
Brute force / Backtracking?
- Yes: With small constraints (at most 16 requests), we can afford to try all possible combinations of requests. We need to explore every subset of requests to find the maximum valid combination.
Conclusion: The flowchart correctly leads us to use a brute force/backtracking approach. The solution uses binary enumeration (a form of brute force) to check all 2^m possible combinations of requests, where each combination is represented by a bitmask. For each combination, we verify if it maintains balance (net change = 0) for all buildings and track the maximum valid combination size.
Intuition
When we first look at this problem, we need to find which transfer requests we can approve while keeping all buildings balanced. The challenge is that approving one request affects two buildings - one loses an employee, another gains one.
The key insight comes from recognizing that we need to find a subset of requests where the movements form "cycles" or balanced patterns. For instance, if person A moves from building 0 to 1, person B moves from 1 to 2, and person C moves from 2 to 0, this forms a cycle where each building loses one and gains one employee.
Since we want the maximum number of requests, we might think about greedy approaches or dynamic programming. However, the constraint that each building must maintain exactly the same number of employees makes it difficult to make local optimal choices. Approving one request might require approving several others to maintain balance, and there's no clear way to predict which combination will be optimal.
The breakthrough comes when we notice the constraint: at most 16 requests. With such a small number, we can actually check every possible combination! If we have m
requests, there are 2^m
ways to select or not select each request. For 16 requests, that's only 65,536 combinations - completely feasible for a computer to check.
We can represent each combination as a binary number where bit i
indicates whether we include request i
. For example, if we have 3 requests and the binary number is 101
, we include requests 0 and 2 but not request 1.
For each combination, we simulate the transfers: subtract 1 from the "from" building and add 1 to the "to" building for each selected request. If all buildings end up with a net change of 0, this combination is valid. Among all valid combinations, we pick the one with the most requests (most 1s in the binary representation).
This brute force approach works perfectly here because the small constraint size allows us to exhaustively search the entire solution space, guaranteeing we find the optimal answer.
Learn more about Backtracking patterns.
Solution Approach
The solution uses binary enumeration to explore all possible combinations of transfer requests. Here's how the implementation works:
Binary Mask Representation:
We use a bitmask to represent which requests are selected. For m
requests, we iterate through all numbers from 0
to 2^m - 1
. Each number's binary representation tells us which requests to include - if bit i
is 1, we include request i
.
Main Loop Structure:
for mask in range(1 << len(requests)):
This iterates through all possible combinations. The expression 1 << len(requests)
equals 2^len(requests)
.
Counting Selected Requests:
cnt = mask.bit_count()
The bit_count()
method returns the number of 1s in the binary representation of mask
, which equals the number of selected requests.
Optimization Check:
if ans < cnt and check(mask):
We only check validity if the current combination has more requests than our current best answer. This saves unnecessary computation.
Validation Function:
The check(mask)
function verifies if a combination maintains balance:
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)
- Initialize a counter array
cnt
with zeros for each building - For each request at index
i
, check if biti
is set inmask
usingmask >> i & 1
- If the request is selected, decrement the count for the "from" building and increment for the "to" building
- Finally, verify all buildings have a net change of 0 using
all(v == 0 for v in cnt)
Time Complexity: O(2^m * m)
where m
is the number of requests. We check 2^m
combinations, and for each, we iterate through m
requests.
Space Complexity: O(n)
for the counter array to track building changes.
The algorithm guarantees finding the optimal solution by exhaustively checking all possibilities, which is feasible due to the small constraint on the number of requests (≤ 16).
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example with n = 3
buildings and requests = [[0,1], [1,2], [0,2]]
.
We need to find the maximum number of these transfer requests we can approve while keeping all buildings balanced (same number of employees).
Step 1: Understanding the Binary Enumeration
With 3 requests, we have 2³ = 8 possible combinations to check:
000
(binary) = 0 (decimal): Select no requests001
(binary) = 1 (decimal): Select only request[2] = [0,2]010
(binary) = 2 (decimal): Select only request[1] = [1,2]011
(binary) = 3 (decimal): Select request[1] and request[2]100
(binary) = 4 (decimal): Select only request[0] = [0,1]101
(binary) = 5 (decimal): Select request[0] and request[2]110
(binary) = 6 (decimal): Select request[0] and request[1]111
(binary) = 7 (decimal): Select all three requests
Step 2: Checking Each Combination
Let's trace through mask = 6 (binary: 110
), which selects requests [0,1] and [1,2]:
- Initialize
cnt = [0, 0, 0]
for buildings 0, 1, and 2 - Process request[0] = [0,1] (bit 0 is set in mask 110):
cnt[0] -= 1
→ cnt = [-1, 0, 0]cnt[1] += 1
→ cnt = [-1, 1, 0]
- Process request[1] = [1,2] (bit 1 is set in mask 110):
cnt[1] -= 1
→ cnt = [-1, 0, 0]cnt[2] += 1
→ cnt = [-1, 0, 1]
- Skip request[2] (bit 2 is not set)
- Check if all values in cnt equal 0: No! Building 0 has -1, building 2 has +1
This combination is invalid.
Step 3: Finding a Valid Combination
Let's check mask = 7 (binary: 111
), which selects all three requests:
- Initialize
cnt = [0, 0, 0]
- Process request[0] = [0,1]:
cnt[0] -= 1
→ cnt = [-1, 0, 0]cnt[1] += 1
→ cnt = [-1, 1, 0]
- Process request[1] = [1,2]:
cnt[1] -= 1
→ cnt = [-1, 0, 0]cnt[2] += 1
→ cnt = [-1, 0, 1]
- Process request[2] = [0,2]:
cnt[0] -= 1
→ cnt = [-2, 0, 1]cnt[2] += 1
→ cnt = [-2, 0, 2]
- Check if all values equal 0: No! Building 0 has -2, building 2 has +2
This is also invalid.
Step 4: Finding the Maximum Valid Combination
After checking all combinations, we find that mask = 0 (no requests) is trivially valid with 0 requests.
For this particular example, no other combination maintains balance. If we had requests like [[0,1], [1,2], [2,0]], then selecting all three would form a cycle where each building loses one and gains one employee, resulting in a valid combination with 3 requests.
The algorithm returns the maximum number of requests from all valid combinations found.
Solution Implementation
1class Solution:
2 def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
3 """
4 Find the maximum number of achievable requests among all requests.
5 A set of requests is achievable if all buildings have net zero change in employees.
6
7 Args:
8 n: Number of buildings (indexed from 0 to n-1)
9 requests: List of [from_building, to_building] transfer requests
10
11 Returns:
12 Maximum number of requests that can be fulfilled while maintaining balance
13 """
14
15 def is_valid_combination(bitmask: int) -> bool:
16 """
17 Check if the selected requests result in balanced employee counts.
18
19 Args:
20 bitmask: Binary representation where bit i indicates if request i is selected
21
22 Returns:
23 True if all buildings have net zero change, False otherwise
24 """
25 # Track net change in employee count for each building
26 building_balance = [0] * n
27
28 # Process each request based on the bitmask
29 for request_idx, (from_building, to_building) in enumerate(requests):
30 # Check if current request is selected (bit is set)
31 if bitmask >> request_idx & 1:
32 building_balance[from_building] -= 1 # Employee leaves
33 building_balance[to_building] += 1 # Employee arrives
34
35 # Check if all buildings have balanced employee count (net zero change)
36 return all(balance == 0 for balance in building_balance)
37
38 max_achievable_requests = 0
39
40 # Try all possible combinations of requests using bitmask
41 # Total combinations = 2^(number of requests)
42 for bitmask in range(1 << len(requests)):
43 # Count number of selected requests in current combination
44 selected_count = bitmask.bit_count()
45
46 # Only check validity if this combination has more requests than current best
47 if max_achievable_requests < selected_count and is_valid_combination(bitmask):
48 max_achievable_requests = selected_count
49
50 return max_achievable_requests
51
1class Solution {
2 private int totalRequests;
3 private int buildingCount;
4 private int[][] transferRequests;
5
6 /**
7 * Find the maximum number of achievable transfer requests.
8 * A set of requests is achievable if the net change in occupancy for each building is 0.
9 *
10 * @param n The number of buildings
11 * @param requests Array of transfer requests where requests[i] = [from, to]
12 * @return Maximum number of achievable requests
13 */
14 public int maximumRequests(int n, int[][] requests) {
15 // Initialize instance variables
16 this.totalRequests = requests.length;
17 this.buildingCount = n;
18 this.transferRequests = requests;
19
20 int maxAchievableRequests = 0;
21
22 // Iterate through all possible subsets of requests using bit masking
23 // Each bit in mask represents whether to include that request (1) or not (0)
24 for (int mask = 0; mask < (1 << totalRequests); ++mask) {
25 // Count the number of requests in current subset
26 int currentRequestCount = Integer.bitCount(mask);
27
28 // Only check if this subset could potentially be better than current maximum
29 if (currentRequestCount > maxAchievableRequests && isValidSubset(mask)) {
30 maxAchievableRequests = currentRequestCount;
31 }
32 }
33
34 return maxAchievableRequests;
35 }
36
37 /**
38 * Check if a subset of requests represented by mask is valid.
39 * A subset is valid if each building has net zero change in occupancy.
40 *
41 * @param mask Bit mask representing which requests to include
42 * @return true if the subset is valid, false otherwise
43 */
44 private boolean isValidSubset(int mask) {
45 // Track net change in occupancy for each building
46 int[] netChange = new int[buildingCount];
47
48 // Process each request based on the mask
49 for (int i = 0; i < totalRequests; ++i) {
50 // Check if the i-th request is included in this subset
51 if ((mask >> i & 1) == 1) {
52 int fromBuilding = transferRequests[i][0];
53 int toBuilding = transferRequests[i][1];
54
55 // Decrease occupancy in source building
56 --netChange[fromBuilding];
57 // Increase occupancy in destination building
58 ++netChange[toBuilding];
59 }
60 }
61
62 // Check if all buildings have net zero change
63 for (int change : netChange) {
64 if (change != 0) {
65 return false;
66 }
67 }
68
69 return true;
70 }
71}
72
1class Solution {
2public:
3 int maximumRequests(int n, vector<vector<int>>& requests) {
4 int numRequests = requests.size();
5 int maxApprovedRequests = 0;
6
7 // Lambda function to check if a subset of requests maintains building balance
8 // A valid subset means each building has net zero employee change
9 auto isValidSubset = [&](int bitmask) -> bool {
10 // Track net employee change for each building
11 int netChange[n];
12 memset(netChange, 0, sizeof(netChange));
13
14 // Process each request if its bit is set in the bitmask
15 for (int i = 0; i < numRequests; ++i) {
16 if (bitmask >> i & 1) {
17 int fromBuilding = requests[i][0];
18 int toBuilding = requests[i][1];
19 --netChange[fromBuilding]; // Employee leaves this building
20 ++netChange[toBuilding]; // Employee enters this building
21 }
22 }
23
24 // Check if all buildings have net zero change
25 for (int change : netChange) {
26 if (change != 0) {
27 return false;
28 }
29 }
30 return true;
31 };
32
33 // Try all possible subsets of requests using bit manipulation
34 // Each bit in mask represents whether to include that request
35 for (int mask = 0; mask < (1 << numRequests); ++mask) {
36 int currentRequestCount = __builtin_popcount(mask); // Count set bits
37
38 // Only check validity if this subset has more requests than current max
39 if (maxApprovedRequests < currentRequestCount && isValidSubset(mask)) {
40 maxApprovedRequests = currentRequestCount;
41 }
42 }
43
44 return maxApprovedRequests;
45 }
46};
47
1/**
2 * Finds the maximum number of requests that can be fulfilled while maintaining
3 * a balanced state (all buildings have net zero employee change)
4 * @param n - Number of buildings
5 * @param requests - Array of transfer requests, each request is [from, to]
6 * @returns Maximum number of achievable requests
7 */
8function maximumRequests(n: number, requests: number[][]): number {
9 const totalRequests = requests.length;
10 let maxAchievableRequests = 0;
11
12 /**
13 * Checks if a given combination of requests results in a balanced state
14 * @param requestMask - Bitmask representing which requests to include
15 * @returns True if all buildings have net zero employee change
16 */
17 const checkBalanced = (requestMask: number): boolean => {
18 // Track net employee change for each building
19 const netChange = Array(n).fill(0);
20
21 // Process each request if its bit is set in the mask
22 for (let requestIndex = 0; requestIndex < totalRequests; ++requestIndex) {
23 if ((requestMask >> requestIndex) & 1) {
24 const [fromBuilding, toBuilding] = requests[requestIndex];
25 // Employee leaves from building
26 --netChange[fromBuilding];
27 // Employee arrives at building
28 ++netChange[toBuilding];
29 }
30 }
31
32 // Check if all buildings have net zero change
33 return netChange.every(change => change === 0);
34 };
35
36 // Try all possible combinations of requests using bitmask
37 for (let requestMask = 0; requestMask < (1 << totalRequests); ++requestMask) {
38 // Count number of requests in current combination
39 const currentRequestCount = bitCount(requestMask);
40
41 // Update maximum if this combination is valid and larger
42 if (maxAchievableRequests < currentRequestCount && checkBalanced(requestMask)) {
43 maxAchievableRequests = currentRequestCount;
44 }
45 }
46
47 return maxAchievableRequests;
48}
49
50/**
51 * Counts the number of set bits (1s) in a number using bit manipulation
52 * Uses Brian Kernighan's algorithm optimized version
53 * @param num - Input number to count bits
54 * @returns Number of set bits
55 */
56function bitCount(num: number): number {
57 // Group bits into pairs and count
58 num = num - ((num >>> 1) & 0x55555555);
59 // Group pairs into nibbles and count
60 num = (num & 0x33333333) + ((num >>> 2) & 0x33333333);
61 // Group nibbles into bytes and count
62 num = (num + (num >>> 4)) & 0x0f0f0f0f;
63 // Sum up bytes
64 num = num + (num >>> 8);
65 num = num + (num >>> 16);
66 // Mask to get final count (max 32 bits, so 6 bits are enough)
67 return num & 0x3f;
68}
69
Time and Space Complexity
Time Complexity: O(2^m × (m + n))
The algorithm uses bit manipulation to enumerate all possible subsets of requests. The outer loop iterates through all 2^m
possible masks (where m
is the length of requests). For each mask:
- The
bit_count()
operation takesO(1)
time in Python 3.10+ - The
check()
function is called, which:- Iterates through all
m
requests to update the count array:O(m)
- Checks if all
n
values in the count array equal zero:O(n)
- Iterates through all
Therefore, the total time complexity is O(2^m × (m + n))
.
Space Complexity: O(n)
The space usage comes from:
- The
cnt
array inside thecheck()
function, which has sizen
:O(n)
- A few integer variables (
ans
,mask
,cnt
) which take constant space:O(1)
The space complexity is O(n)
as the dominant factor is the count array used to track the net change in occupancy for each room.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Misunderstanding the Balance Constraint
Many developers initially think that simply matching the total number of outgoing and incoming transfers is sufficient. However, the constraint requires each individual building to maintain its exact employee count.
Incorrect approach:
# Wrong: Only checking total balance
total_in = sum(1 for _, to_building in selected_requests)
total_out = sum(1 for from_building, _ in selected_requests)
return total_in == total_out # This is NOT sufficient!
Correct approach:
# Right: Check balance for EACH building independently
building_balance = [0] * n
for from_building, to_building in selected_requests:
building_balance[from_building] -= 1
building_balance[to_building] += 1
return all(balance == 0 for balance in building_balance)
2. Incorrect Bit Manipulation
A common mistake is incorrectly checking if a bit is set in the mask, leading to wrong request selections.
Incorrect approaches:
# Wrong: Using wrong bit shift direction
if mask << i & 1: # Should be >> not <<
# Wrong: Forgetting the & 1 operation
if mask >> i: # This checks if mask >> i is non-zero, not if bit i is set
# Wrong: Using wrong bit index
if mask & (1 << (len(requests) - i - 1)): # Unnecessarily reversing bit order
Correct approach:
# Right: Shift right by i positions and check the least significant bit if mask >> i & 1: # Process request i
3. Off-by-One Error in Enumeration Range
Developers might incorrectly calculate the total number of combinations.
Incorrect approach:
# Wrong: Missing the last combination
for mask in range((1 << len(requests)) - 1): # Misses the all-1s combination
# Wrong: Including unnecessary iteration
for mask in range(1 << len(requests) + 1): # One iteration too many
Correct approach:
# Right: Range from 0 to 2^m - 1 (inclusive)
for mask in range(1 << len(requests)):
# This covers all 2^m combinations
4. Inefficient Order of Operations
Checking validity before comparing with the current best answer wastes computation.
Inefficient approach:
for mask in range(1 << len(requests)):
if is_valid_combination(mask): # Expensive check done first
selected_count = mask.bit_count()
if selected_count > max_achievable_requests:
max_achievable_requests = selected_count
Efficient approach:
for mask in range(1 << len(requests)):
selected_count = mask.bit_count() # Cheap operation first
if selected_count > max_achievable_requests: # Quick filter
if is_valid_combination(mask): # Expensive check only when needed
max_achievable_requests = selected_count
5. Handling Self-Transfers Incorrectly
When an employee requests to transfer from building A to building A (same building), this still counts as a valid request that can be fulfilled without affecting the balance.
Potential confusion:
# Some might think self-transfers need special handling if from_building == to_building: # Special case? No! The balance logic handles this automatically # building_balance[from_building] -= 1 # building_balance[from_building] += 1 # Net effect is 0, which is correct
Correct understanding: The standard balance tracking automatically handles self-transfers correctly since subtracting 1 and adding 1 to the same building results in no net change.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!