LeetCode 1601 - Maximum Number of Achievable Transfer Requests

Difficulty: 🔴 Hard
Topics: Array, Backtracking, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem asks us to maximize the number of employee transfer requests that can be fulfilled under the constraint that the total number of employees in each building remains constant. Each request is represented as a pair [from, to], indicating an employee wants to move from building from to building to. The challenge is that all buildings are fully occupied, so for any subset of requests we choose to approve, the net change of employees for every building must be zero. In other words, the number of employees leaving a building must equal the number moving in.

The input includes the number of buildings n and a list of requests. The output is a single integer: the maximum number of requests that can be simultaneously fulfilled while keeping each building's population unchanged.

Constraints give us helpful information about the problem's scale. With n <= 20 and requests.length <= 16, we can consider approaches that might be exponential in the number of requests but not in n. This hints that an enumeration or bitmask approach could be feasible.

Important edge cases include requests where employees want to stay in the same building, which are always achievable, and situations where requests form cycles, allowing multiple employees to be swapped without violating the net-zero constraint.

Approaches

A brute-force approach would examine all subsets of requests. For each subset, we compute the net change for every building and check if all changes are zero. If so, we update the maximum count of requests fulfilled. While correct, this approach has a worst-case complexity of O(2^m * n) where m is the number of requests, which is acceptable given the constraint m <= 16.

The key observation for optimization is that requests.length is small. We can use a backtracking approach that incrementally explores each request, deciding whether to include it in the current solution. We track the net employee change in each building dynamically. If we reach a configuration where all net changes are zero, we update the maximum count. This avoids recomputing changes for every subset and allows pruning in some implementations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m * n)	O(n)	Examine all subsets of requests and verify net-zero condition
Backtracking / Bitmask	O(2^m * n)	O(n)	Incrementally build valid subsets; practical due to small m

Algorithm Walkthrough

Initialize an array delta of size n to track the net change of employees in each building.
Define a recursive backtracking function that takes the current index in requests and the count of requests chosen so far.
At each step, we have two choices: either include the current request or skip it.
If we include a request [from, to], increment delta[to] by 1 and decrement delta[from] by 1.
Recursively call the function for the next index.
After exploring inclusion, undo the changes to delta to backtrack and explore the skip option.
When the index reaches the end of requests, check if all elements in delta are zero. If so, update the maximum count.
Return the maximum count found after exploring all subsets.

Why it works: By exploring all subsets and checking the net-zero constraint, we ensure we consider every possible valid combination of requests. The recursive backtracking ensures that the state of net changes is correctly maintained and reverted, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        delta = [0] * n
        max_requests = 0
        
        def backtrack(index: int, count: int):
            nonlocal max_requests
            if index == len(requests):
                if all(d == 0 for d in delta):
                    max_requests = max(max_requests, count)
                return
            from_building, to_building = requests[index]
            
            # Include the request
            delta[from_building] -= 1
            delta[to_building] += 1
            backtrack(index + 1, count + 1)
            
            # Backtrack
            delta[from_building] += 1
            delta[to_building] -= 1
            
            # Skip the request
            backtrack(index + 1, count)
        
        backtrack(0, 0)
        return max_requests

The implementation defines a helper backtrack function that explores every subset of requests. The delta array keeps track of net changes for each building. For each request, we recursively try including it and skipping it, updating delta accordingly. At the end of each path, we check if all net changes are zero to update the maximum count.

Go Solution

func maximumRequests(n int, requests [][]int) int {
    delta := make([]int, n)
    maxRequests := 0
    
    var backtrack func(index int, count int)
    backtrack = func(index int, count int) {
        if index == len(requests) {
            valid := true
            for _, d := range delta {
                if d != 0 {
                    valid = false
                    break
                }
            }
            if valid && count > maxRequests {
                maxRequests = count
            }
            return
        }
        
        from, to := requests[index][0], requests[index][1]
        
        // Include the request
        delta[from]--
        delta[to]++
        backtrack(index+1, count+1)
        
        // Backtrack
        delta[from]++
        delta[to]--
        
        // Skip the request
        backtrack(index+1, count)
    }
    
    backtrack(0, 0)
    return maxRequests
}

In Go, we use a slice delta to track net changes and a nested function backtrack for recursion. The logic mirrors Python: for each request, we try including it and skipping it, updating delta appropriately. Go’s slice semantics require explicit backtracking to restore state, which is handled similarly to Python.

Worked Examples

Example 1: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]

Index	Request	Include?	delta state	Max count
0	[0,1]	Yes	[-1,1,0,0,0]	1
1	[1,0]	Yes	[0,0,0,0,0]	2
2	[0,1]	Yes	[-1,1,0,0,0]	3
3	[1,2]	Yes	[-1,0,1,0,0]	4
4	[2,0]	Yes	[0,0,0,0,0]	5
5	[3,4]	Skip	[0,0,0,0,0]	5

Maximum achievable requests = 5

Example 2: n = 3, requests = [[0,0],[1,2],[2,1]]

All requests form a valid net-zero configuration, maximum achievable requests = 3

Example 3: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]

All requests form a cycle, net-zero configuration achievable, maximum requests = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^m * n)	We explore all subsets of requests (2^m) and for each, we check/modify net change for n buildings
Space	O(n)	Only the delta array of size n is maintained plus recursion stack depth O(m)

The exponential factor is manageable because m <= 16. Each subset operation involves updating a delta array of size n.

Test Cases

# Provided examples
assert Solution().maximumRequests(5, [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]) == 5  # complex swaps
assert Solution().maximumRequests(3, [[0,0],[1,2],[2,1]]) == 3  # self-transfer and simple cycle
assert Solution().maximumRequests(4, [[0,3],[3,1],[1,2],[2,0]]) == 4  # cycle covering all buildings

# Edge cases
assert Solution().maximumRequests(1, [[0,0]]) == 1  # single building, self-transfer
assert Solution().maximumRequests(2, [[0,1],[1,0]]) == 2  # simple swap
assert Solution().maximumRequests(3, [[0,1],[0,2],[1,2]]) == 2  # max achievable without breaking net-zero
assert Solution().maximumRequests(20, [[i, (i+1)%20] for i in range(16)]) == 16  # large n, maximum requests used

Test	Why
complex swaps	tests ability to pick correct subset of interleaving requests
self-transfer	ensures requests where from = to are handled
cycle covering all buildings	tests circular dependency handling
single building	minimal n and request
simple swap