Problem Description

You are given n buildings numbered from 0 to n - 1 and a list of transfer requests where each request is represented as [from, to]. Each request means an employee wants to move from building from to building to. You need to select the maximum number of requests such that after performing all selected requests, the net change in employees for every building is zero (i.e., for every building, the number of people leaving equals the number entering).

• Each request can be used at most once.
• Return the largest possible number of requests that can be achieved under the above condition.
• Constraints: 1 ≤ n ≤ 20, 1 ≤ requests.length ≤ 16

Thought Process

The core of this problem is to select a subset of requests such that, for every building, the number of incoming and outgoing employees is balanced.
A brute-force approach would be to check every possible combination of requests and see if it results in a balanced state for all buildings. Since the number of requests is small (up to 16), this is feasible. However, we want to avoid unnecessary computations and optimize where possible.

The first insight is that the problem can be modeled as a subset selection problem: for each request, decide whether to include it or not. For each subset, we can simulate the net change for each building and check if all net changes are zero.
The challenge is to efficiently check all possible subsets and keep track of the maximum number that can be chosen.

Solution Approach

Here’s how we solve the problem step by step:

1. Enumerate all subsets: Since there are at most 16 requests, we can use a bitmask (from 0 to 2^{requests.length} - 1) to represent every possible subset of requests.
2. Simulate transfers for each subset: For each subset, we maintain an array net of size n representing the net change of employees for each building. For every request in the subset, decrement net[from] and increment net[to].
3. Check for balance: After simulating the subset, check if all elements in net are zero. If so, update the answer with the maximum number of requests used so far.
4. Optimize with pruning (optional): Since we are checking all subsets, no further optimization is necessary given the constraints, but we can skip checking subsets with fewer requests than the current best answer.

We use this approach because the number of possible subsets (2¹⁶ = 65536) is manageable, and each subset check is efficient.

Example Walkthrough

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

1. Enumerate all possible subsets of requests (there are 64 in total for 6 requests).
2. For each subset, calculate the net change for each building:
   • Suppose we select requests 0, 1, 2 ([[0,1],[1,2],[2,0]]):
     • Request [0,1]: net[0] -= 1, net[1] += 1
     • Request [1,2]: net[1] -= 1, net[2] += 1
     • Request [2,0]: net[2] -= 1, net[0] += 1
     After processing: net = [0, 0, 0] (balanced!)
3. Count the number of requests used (3 in this case). Keep track of the maximum found so far.
4. Continue until all subsets are checked. The maximum for this example is 6 (all requests can be used).

Time and Space Complexity

• Brute-force approach: We check every subset of requests. For k requests, there are 2^k subsets. For each subset, we simulate up to k requests and maintain a net array of size n.
• Time Complexity: O(2^k * k), where k is the number of requests. For the maximum case (k=16), this is about 1 million operations.
• Space Complexity: O(n) for the net array used in each simulation.
• Optimized Approach: No further optimization is necessary given the constraints.

Summary

The problem reduces to selecting the largest subset of requests so that each building's net employee change is zero. By enumerating all possible subsets and checking for balance, we can efficiently solve the problem due to the small input size. The key insight is recognizing that a brute-force subset check is feasible and effective here, making the solution both simple and elegant.

Code Implementation

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        m = len(requests)
        max_req = 0
        for mask in range(1 << m):
            net = [0] * n
            count = 0
            for i in range(m):
                if (mask >> i) & 1:
                    from_b, to_b = requests[i]
                    net[from_b] -= 1
                    net[to_b] += 1
                    count += 1
            if all(x == 0 for x in net):
                max_req = max(max_req, count)
        return max_req
      

class Solution {
public:
    int maximumRequests(int n, vector<vector<int>>& requests) {
        int m = requests.size(), ans = 0;
        for (int mask = 0; mask < (1 << m); ++mask) {
            vector<int> net(n, 0);
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if ((mask >> i) & 1) {
                    net[requests[i][0]]--;
                    net[requests[i][1]]++;
                    cnt++;
                }
            }
            bool ok = true;
            for (int val : net) {
                if (val != 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) ans = max(ans, cnt);
        }
        return ans;
    }
};
      

class Solution {
    public int maximumRequests(int n, int[][] requests) {
        int m = requests.length, maxReq = 0;
        for (int mask = 0; mask < (1 << m); ++mask) {
            int[] net = new int[n];
            int count = 0;
            for (int i = 0; i < m; ++i) {
                if (((mask >> i) & 1) == 1) {
                    net[requests[i][0]]--;
                    net[requests[i][1]]++;
                    count++;
                }
            }
            boolean ok = true;
            for (int x : net) {
                if (x != 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) maxReq = Math.max(maxReq, count);
        }
        return maxReq;
    }
}
      

var maximumRequests = function(n, requests) {
    let m = requests.length, maxReq = 0;
    for (let mask = 0; mask < (1 << m); ++mask) {
        let net = Array(n).fill(0);
        let count = 0;
        for (let i = 0; i < m; ++i) {
            if ((mask >> i) & 1) {
                net[requests[i][0]]--;
                net[requests[i][1]]++;
                count++;
            }
        }
        if (net.every(x => x === 0)) {
            maxReq = Math.max(maxReq, count);
        }
    }
    return maxReq;
};