Maximum Number of Achievable Transfer Requests

Maximum Number of Achievable Transfer Requests - Problem

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It's transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [from_i, to_i] represents an employee's request to transfer from building from_i to building to_i.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in.

Return the maximum number of achievable transfer requests.

Input & Output

Example 1 — Balanced Transfers

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

› Output: 5

💡 Note: We can accept requests [0,1],[1,0],[0,1],[1,2],[2,0]. Net changes: building 0: -1+1-1+1=1-1=0, building 1: +1-1+1-1=0, building 2: +1-1=0, buildings 3,4 unchanged=0. All buildings balanced.

Example 2 — Simple Case

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

› Output: 3

💡 Note: All requests can be accepted: [0,0] is self-transfer (no net change), [1,2] and [2,1] cancel each other out. Net changes all zero.

Example 3 — No Valid Subset

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

› Output: 2

💡 Note: Both requests can be accepted since they involve different pairs of buildings. Building 0: -1, building 1: +1, building 2: -1, building 3: +1. All balanced.

Constraints

1 ≤ n ≤ 20
1 ≤ requests.length ≤ 16
requests[i].length == 2
0 ≤ from_i, to_i < n

Visualization

Tap to expand

Understanding the Visualization

Input

Buildings and transfer requests between them

Process

Find subset where each building has zero net change

Output

Maximum number of achievable requests

Key Takeaway

🎯 Key Insight: Valid transfers require each building to have equal employees leaving and entering

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that valid transfers require zero net change for each building. Best approach is backtracking with pruning to efficiently explore all possible request subsets. Time: O(2^m), Space: O(n + m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(2^m × n)	O(n)	Generate all possible subsets of requests and check validity
Backtracking with Pruning	O(2^m)	O(n + m)	Use recursive backtracking to explore valid combinations efficiently

Brute Force - Try All Subsets — Algorithm Steps

Generate all 2^m subsets of requests
For each subset, count net transfers per building
Check if all buildings have zero net change
Return size of largest valid subset

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^m possible subsets of requests

Check Balance

For each subset, verify net change is zero for all buildings

Find Maximum

Return size of largest valid subset

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, int requests[][2], int m) {
    int maxRequests = 0;
    
    // Try all possible subsets using bit manipulation
    for (int mask = 0; mask < (1 << m); mask++) {
        // Count net changes for each building
        int netChange[20] = {0}; // Assuming n <= 20
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                int fromBuilding = requests[i][0];
                int toBuilding = requests[i][1];
                netChange[fromBuilding]--;
                netChange[toBuilding]++;
                count++;
            }
        }
        
        // Check if all buildings have zero net change
        int valid = 1;
        for (int i = 0; i < n; i++) {
            if (netChange[i] != 0) {
                valid = 0;
                break;
            }
        }
        
        if (valid && count > maxRequests) {
            maxRequests = count;
        }
    }
    
    return maxRequests;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    // Parse 2D array manually
    int requests[16][2]; // Assuming max 16 requests
    int m = 0;
    
    char *ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            requests[m][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            requests[m][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            m++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, requests, m);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m × n)

2^m subsets to check, each takes O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Array to track net changes per building

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler