Facebook Pixel

1601. Maximum Number of Achievable Transfer Requests

HardBit ManipulationArrayBacktrackingEnumeration
Leetcode Link

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 bit i is set in mask using mask >> 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 Evaluator

Example 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 requests
  • 001 (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]:

  1. Initialize cnt = [0, 0, 0] for buildings 0, 1, and 2
  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]
  3. 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]
  4. Skip request[2] (bit 2 is not set)
  5. 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:

  1. Initialize cnt = [0, 0, 0]
  2. Process request[0] = [0,1]:
    • cnt[0] -= 1 → cnt = [-1, 0, 0]
    • cnt[1] += 1 → cnt = [-1, 1, 0]
  3. Process request[1] = [1,2]:
    • cnt[1] -= 1 → cnt = [-1, 0, 0]
    • cnt[2] += 1 → cnt = [-1, 0, 1]
  4. Process request[2] = [0,2]:
    • cnt[0] -= 1 → cnt = [-2, 0, 1]
    • cnt[2] += 1 → cnt = [-2, 0, 2]
  5. 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 takes O(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)

Therefore, the total time complexity is O(2^m × (m + n)).

Space Complexity: O(n)

The space usage comes from:

  • The cnt array inside the check() function, which has size n: 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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More