Maximum Number of Achievable Transfer Requests

Hard
1594.

Maximum Number of Achievable Transfer Requests

Maximum Number of Achievable Transfer Requests is a hard coding problem on arrays, bit manipulation and backtracking, asked in Amazon and Google interviews.

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 <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= from_i, to_i < n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} requests
 * @return {number}
 */
var maximumRequests = function(n, requests) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= from_i, to_i < n

Hints for Maximum Number of Achievable Transfer Requests

  1. Hint 1

    There are at most 16 requests, so every subset of them can be examined.

  2. 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.

  3. 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

  1. Keep delta[b] for each building, all zero at the start.
  2. dfs(i, taken): if i == len(requests), update the answer with taken when every delta is zero.
  3. If taken + (remaining requests) <= best, return early.
  4. Take request i (delta[from]--, delta[to]++, recurse with taken + 1, undo), then skip it (recurse with taken).

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