Maximum Number of Achievable Transfer Requests — Solution
Maximum Number of Achievable Transfer Requests solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Achievable Transfer Requests is a hard coding problem on arrays, bit manipulation and backtracking, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Bit Manipulation, Backtracking, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n buildings, numbered 0 to n - 1, and every building is full. Each requests[i] = [from, to] is an employee asking to move from building from to building to (possibly the same building).
You may approve any subset of the requests, but because the buildings are full, the approved set must leave every building's headcount unchanged: for each building, the number of approved employees leaving it equals the number of approved employees arriving.
Return the maximum number of requests you can approve.
Example 1
Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explanation: Approve every request except `[3,4]`: buildings 0, 1 and 2 each lose and gain the same number of people.
Example 2
Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Example 3
Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4
Explanation: The four moves form one cycle.
Constraints
1 <= n <= 201 <= requests.length <= 16requests[i].length == 20 <= from_i, to_i < n
Hints for Maximum Number of Achievable Transfer Requests
Hint 1
There are at most 16 requests, so every subset of them can be examined.
Hint 2
For a chosen subset, track the net change of every building (−1 for each departure, +1 for each arrival). The subset is valid when every net change is 0.
Hint 3
Backtrack request by request (take it or skip it), updating the net changes as you go, and stop exploring a branch once even taking every remaining request could not beat the best answer so far.
How to solve Maximum Number of Achievable Transfer Requests
With at most 16 requests, enumerate every subset — by backtracking over take/skip decisions with an incrementally maintained balance per building — and keep the largest balanced one.
Approach
- Keep
delta[b]for each building, all zero at the start. dfs(i, taken): ifi == len(requests), update the answer withtakenwhen everydeltais zero.- If
taken + (remaining requests) <= best, return early. - Take request
i(delta[from]--,delta[to]++, recurse withtaken + 1, undo), then skip it (recurse withtaken).
Why it works
A set of approved moves keeps every building full exactly when each building's departures equal its arrivals, i.e. all net changes are zero. The search inspects every subset that could still beat the current best, so it finds the maximum.
Complexity
- Time —
O(2^m · n) for m requests - Space —
O(n + m)
Pitfalls
- A request from a building to itself is always approvable — it never changes the balance.
- Checking only that the total balance is zero is not enough; every building must balance on its own.
- Skipping the bound is fine for correctness but much slower.
Reference solution
Python
from typing import List
def maximumRequests(n: int, requests: List[List[int]]) -> int:
m = len(requests)
delta = [0] * n
best = [0]
def dfs(i, taken):
if i == m:
if taken > best[0] and all(d == 0 for d in delta):
best[0] = taken
return
if taken + (m - i) <= best[0]:
return
a, b = requests[i]
delta[a] -= 1
delta[b] += 1
dfs(i + 1, taken + 1)
delta[a] += 1
delta[b] -= 1
dfs(i + 1, taken)
dfs(0, 0)
return best[0]Java
static int transferBest;
public static int maximumRequests(int n, int[][] requests) {
transferBest = 0;
transferDfs(requests, new int[n], 0, 0);
return transferBest;
}
static void transferDfs(int[][] req, int[] delta, int i, int taken) {
if (i == req.length) {
if (taken > transferBest) {
for (int d : delta) if (d != 0) return;
transferBest = taken;
}
return;
}
if (taken + (req.length - i) <= transferBest) return;
delta[req[i][0]]--;
delta[req[i][1]]++;
transferDfs(req, delta, i + 1, taken + 1);
delta[req[i][0]]++;
delta[req[i][1]]--;
transferDfs(req, delta, i + 1, taken);
}C++
void transferDfs(vector<vector<int>>& req, vector<int>& delta, int i, int taken, int& best) {
if (i == (int)req.size()) {
if (taken > best) {
for (int d : delta) if (d != 0) return;
best = taken;
}
return;
}
if (taken + ((int)req.size() - i) <= best) return;
delta[req[i][0]]--;
delta[req[i][1]]++;
transferDfs(req, delta, i + 1, taken + 1, best);
delta[req[i][0]]++;
delta[req[i][1]]--;
transferDfs(req, delta, i + 1, taken, best);
}
int maximumRequests(int n, vector<vector<int>>& requests) {
vector<int> delta(n, 0);
int best = 0;
transferDfs(requests, delta, 0, 0, best);
return best;
}JavaScript
var maximumRequests = function(n, requests) {
var m = requests.length;
var delta = new Array(n).fill(0);
var best = 0;
var dfs = function(i, taken) {
if (i === m) {
if (taken > best) {
for (var b = 0; b < n; b++) if (delta[b] !== 0) return;
best = taken;
}
return;
}
if (taken + (m - i) <= best) return;
var from = requests[i][0], to = requests[i][1];
delta[from]--;
delta[to]++;
dfs(i + 1, taken + 1);
delta[from]++;
delta[to]--;
dfs(i + 1, taken);
};
dfs(0, 0);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation