1601. Maximum Number of Achievable Transfer Requests

HardBit ManipulationArrayBacktrackingEnumeration
Leetcode Link

Problem Description

We are given n buildings, and an array of employee transfer requests between these buildings. Each request is represented by a pair [from, to], meaning an employee wants to transfer from one building to another. A request array is deemed achievable if the transfers can happen without altering the total number of employees in each building; that is to say, the incoming employees must balance the outgoing ones for every building. The objective is to return the maximum number of such achievable transfer requests.

To put it simply, we have to find the largest subset of the given requests that can be satisfied simultaneously, ensuring that every building ends up with the same number of employees it started with.

Intuition

The solution approach is based on the idea of checking every possible combination of requests, from no requests being satisfied to all of them being considered. To do this efficiently, a bitmask representation is utilized.

A bitmask approach involves creating a mask for each possible subset of requests. Each bit in the mask corresponds to a decision whether to include or exclude a particular request. The total number of bitmasks to check will be 2^len(requests), because that's how many subsets are possible.

The intuition behind using a bitmask is that it allows us to efficiently iterate over all subsets of requests, including the empty set and the set containing all requests. By incrementally checking each bitmask, we determine whether that particular combination of requests leads to a balanced transfer where each building's employee count remains unchanged.

Checking a mask involves updating a list of net change in employees for each building (cnt). If a request is included in the mask (indicated by the corresponding bit being 1), we decrement the employees count from the from building and increment it in the to building. At the end of this process, we check if all buildings' counts are zero. If they are, it means that particular combination is achievable.

The final step keeps track of the maximum number of requests that form a valid set (ans). This is done by comparing the number of requests in the current mask (cnt) with the highest number found so far. If the current mask is both a larger set and a valid transfer set, it updates the maximum found.

This brute force method ensures that all possible request combinations are checked, and the largest valid subset is found.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The implementation of the solution employs a brute force approach with a bit manipulation technique to iterate through all possible subsets of the transfer requests.

Here’s the step-by-step breakdown of the code:

  1. Define a helper function check(mask: int) -> bool:

    • This function takes a bitmask as an argument, representing a subset of requests.
    • It creates an array cnt of size n, initialized with zeros. The array represents the net change in the number of employees in each building.
    • The function iterates over all requests and for each request, checks if the corresponding bit in the mask is set to 1. If it is, it means the request is included in the current subset and the function updates the cnt array by decrementing the count for the from building and incrementing it for the to building.
    • After iterating through all requests, it checks if all buildings have a net change of zero, and returns True if they do, indicating that the subset is achievable.

  2. Initialize a variable ans with 0 to keep track of the maximum number of achievable requests found.

  3. Iterate through all possible masks/subsets using a for-loop:

    • The range of the loop is 1 << len(requests), which gives us all possible combinations of including or excluding each request.
    • The variable mask represents the current subset of requests being considered.

  4. Inside the loop, calculate the number of requests included in the current subset using mask.bit_count(), which returns the number of set bits (or 1s) in the bitmask.

  5. If the current mask has more requests than ans (the previous maximum), and the check(mask) function confirms that the current subset is achievable, update ans with the count of the current subset.

  6. After considering all possible subsets, return ans as the final result. This value represents the maximum number of requests that can be accommodated without changing the number of employees in each building.

Overall, the key data structures used in this approach are:

  • An integer mask to represent a subset of requests and facilitate bit manipulation.
  • An array cnt for tracking the net change in employees for each building within a subset.

This algorithm makes use of combinatorial logic (to generate all possible subsets of requests) and bitwise operations (to manage and evaluate these subsets efficiently). The time complexity of this approach is O(2^m * n) where m is the number of requests and n is the number of buildings, since for each of the 2^m subsets, we perform n operations to validate it.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's take a small example to illustrate the solution approach.

Suppose we have n = 3 buildings and a list of 4 employee transfer requests, as follows:

1requests = [[0, 1], [1, 2], [0, 2], [2, 0]]

Here's a step-by-step walkthrough using a bitmask approach for the given requests:

  1. Initialize Maximum Achievable Requests (ans):

    We start by setting ans to 0, as we have not processed any requests yet.

  2. Iterate Through All Possible Subsets:

    With 4 requests, there are 2^4 = 16 possible combinations of these requests, from no requests (bitmask 0000) to all requests (bitmask 1111).

  3. Evaluate Each Subset (Bitmask):

    For each bitmask, we perform the following steps:

    • Bitmask 0000: No requests are included, thus ans remains 0.
    • Bitmask 0001: The subset includes just the last request [2, 0]. This is achievable as we can transfer one employee from building 2 to 0.
    • Bitmask 0010: The subset includes the request [0, 2]. This is also achievable in isolation, but ans remains at 1 because we already found a subset of 1 request.
    • ...and so on for each combination...
    • Bitmask 1011: This subset includes requests [0, 1], [1, 2], and [0, 2]. Upon checking, the count for each building after these transfers would be 0, so the subset is achievable. Since this subset has 3 transfers, ans is updated to 3.

  4. Check Each Subset For Balance (Using check Function):

    When we evaluate each set, the check function will update an array cnt that tracks the net change in number of employees at each building, considering which requests are included in the current subset. If all entries in cnt are 0, it means that the current subset of requests is balanced and thus achievable.

  5. Find Maximum Number of Achievable Requests:

    As we evaluate all possible subsets, we use the ans variable to keep track of the greatest number of requests in a balanced subset encountered so far. In our example, upon checking all subsets, the maximum achievable number is 3, which would be the final answer.

For this example, the final ans represents that there is a subset of 3 transfer requests which can be satisfied simultaneously, maintaining the balance of employees in all buildings.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
5        # Internal function to check if the current combination of requests
6        # satisfies the balance of incoming and outgoing requests for each building.
7        def is_valid(combination: int) -> bool:
8            balance = [0] * n  # Initialize a list to keep track of balance for each building
9            for idx, (from_building, to_building) in enumerate(requests):
10                if combination >> idx & 1:  # If the current request is included in the combination
11                    balance[from_building] -= 1  # Decrement the balance for the 'from' building
12                    balance[to_building] += 1  # Increment the balance for the 'to' building
13            return all(value == 0 for value in balance)  # Return True if all balances are zero
14      
15        maximum_val = 0  # Initialize the maximum number of requests that can be satisfied
16
17        # Iterate over all possible combinations of requests represented by bitmask
18        for combination in range(1 << len(requests)):  # 1 << len(requests) is 2 raised to the power of the number of requests
19            count = bin(combination).count('1')  # Count how many requests are included in this combination
20            if maximum_val < count and is_valid(combination):  # If this combination has more requests than the max found so far, and is valid
21                maximum_val = count  # Update the maximum value
22      
23        return maximum_val  # Return the maximum number of requests that can be satisfied
24
25# Example usage:
26# sol = Solution()
27# result = sol.maximumRequests(n, requests)
28# where 'n' is the number of buildings and 'requests' is the list of request pairs [from, to].
29
1class Solution {
2    private int numRequests; // Total number of requests
3    private int numBuildings; // Total number of buildings
4    private int[][] requestsArray; // Array containing requests
5
6    public int maximumRequests(int numBuildings, int[][] requestsArray) {
7        this.numRequests = requestsArray.length;
8        this.numBuildings = numBuildings;
9        this.requestsArray = requestsArray;
10        int maxRequests = 0; // Maximum number of requests that can be fulfilled without imbalance
11
12        // Iterate over all possible combinations of requests
13        for (int mask = 0; mask < (1 << numRequests); ++mask) {
14            int requestCount = Integer.bitCount(mask); // Count of requests in the current combination
15            // If the current combination has more requests and is balanced, update maxRequests
16            if (maxRequests < requestCount && isBalanced(mask)) {
17                maxRequests = requestCount;
18            }
19        }
20        return maxRequests; // Return the maximum number of requests that can be fulfilled
21    }
22
23    // Helper method to check if a combination of requests is balanced
24    private boolean isBalanced(int mask) {
25        int[] balance = new int[numBuildings]; // Array to keep track of the balance of each building
26
27        // Apply requests in the current combination to the balance array
28        for (int i = 0; i < numRequests; ++i) {
29            if ((mask >> i & 1) == 1) { // If the i-th request is in the combination
30                int from = requestsArray[i][0], to = requestsArray[i][1];
31                --balance[from]; // Decrement the count of the 'from' building
32                ++balance[to]; // Increment the count of the 'to' building
33            }
34        }
35
36        // Check if all buildings are balanced, i.e., have a zero balance
37        for (int v : balance) {
38            if (v != 0) {
39                return false; // If any building is unbalanced, return false
40            }
41        }
42        return true; // If all buildings are balanced, return true
43    }
44}
45
1#include <vector>
2#include <cstring> // for memset
3
4class Solution {
5public:
6    // Function to find the maximum number of requests that can be fulfilled without leaving any building imbalanced.
7    int maximumRequests(int n, std::vector<std::vector<int>>& requests) {
8        int requestCount = requests.size();
9        int maxFulfilledRequests = 0; // Variable to store the maximum number of requests fulfilled.
10
11        // Lambda function to check if the selected requests sequence balances the building.
12        auto checkBalance = [&](int mask) -> bool {
13            int balance[n]; // Array to hold the net balance of each building.
14            std::memset(balance, 0, sizeof(balance)); // Initialize all balances to zero.
15
16            for (int i = 0; i < requestCount; ++i) { // Traverse each request.
17                if (mask >> i & 1) { // Check if the i-th request is chosen in the current combination (mask).
18                    int from = requests[i][0], to = requests[i][1]; // Get the 'from' and 'to' buildings for the request.
19                    --balance[from]; // Decrement balance for the 'from' building.
20                    ++balance[to]; // Increment balance for the 'to' building.
21                }
22            }
23
24            // Check if all buildings are balanced, i.e., have a net balance of zero.
25            for (int value : balance) {
26                if (value) { // If any building is not balanced, return false.
27                    return false;
28                }
29            }
30            return true; // All buildings are balanced, return true.
31        };
32
33        // Iterate over all combinations of requests.
34        for (int mask = 0; mask < (1 << requestCount); ++mask) {
35            int currentCount = __builtin_popcount(mask); // Count the number of bits set in mask, which equals the number of requests chosen.
36            // If the current combination has more requests than maxFulfilledRequests and is balanced.
37            if (maxFulfilledRequests < currentCount && checkBalance(mask)) { 
38                maxFulfilledRequests = currentCount; // Update the maximum number of requests fulfilled.
39            }
40        }
41        // Return the final answer, which is the maximum number of requests that can be fulfilled.
42        return maxFulfilledRequests;
43    }
44};
45
1// Function to calculate the maximum number of requests that can be fulfilled without any building ending up in a deficit.
2function maximumRequests(n: number, requests: number[][]): number {
3    const numberOfRequests = requests.length;
4    let maximumFulfilledRequests = 0;
5
6    // Function to check if the given combination of requests keeps all buildings balanced.
7    const checkBalancedRequests = (mask: number): boolean => {
8        const balanceCounter = new Array(n).fill(0);
9        for (let i = 0; i < numberOfRequests; ++i) {
10            if ((mask >> i) & 1) {
11                const [fromBuilding, toBuilding] = requests[i];
12                // Decrement for the 'from' building, and increment for the 'to' building.
13                --balanceCounter[fromBuilding];
14                ++balanceCounter[toBuilding];
15            }
16        }
17        // Check if all the buildings are balanced (end up with 0 transfers).
18        return balanceCounter.every(value => value === 0);
19    };
20
21    // Iterate over all possible combinations of requests.
22    for (let mask = 0; mask < (1 << numberOfRequests); ++mask) {
23        const numberOfSetBits = bitCount(mask);  // Count the number of bits set in mask.
24        if (maximumFulfilledRequests < numberOfSetBits && checkBalancedRequests(mask)) {
25            maximumFulfilledRequests = numberOfSetBits;  // Update max if a better combination is found.
26        }
27    }
28    return maximumFulfilledRequests;  // Return the maximum number of requests that can be fulfilled.
29}
30
31// Function to count the number of bits set to 1 in the binary representation of a number.
32function bitCount(i: number): number {
33    i = i - ((i >>> 1) & 0x55555555);
34    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
35    i = (i + (i >>> 4)) & 0x0f0f0f0f;
36    i = i + (i >>> 8);
37    i = i + (i >>> 16);
38    return i & 0x3f;  // Return the number of bits set.
39}
40
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by two nested operations:

  1. The outer loop, which iterates over all possible subsets of requests. There are len(requests) requests, and for each request, there are two possibilities (either the request is fulfilled or it is not). Therefore, there are 2^(len(requests)) possible subsets, resulting in a time complexity of O(2^m) for this loop, where m is the length of requests.

  2. The inner function check(mask), which is called for each subset to verify whether choosing a particular subset of requests satisfies the balance criterion (every building ends up with the same number of people). This function iterates through all requests and then all buildings to ensure balance, contributing a complexity of O(m + n), where n is the number of buildings.

The combined effect of these operations leads to a total time complexity of O(2^m * (m + n)).

Space Complexity

The space complexity of the provided code can be analyzed by looking at the additional memory used by the algorithm. The key factors influencing space complexity here are:

  1. The counter array cnt for building balances, which uses O(n) space, where n is the number of buildings.

  2. The bit mask, which does not add significant space complexity, as it is just an integer value storing the current subset being checked.

Thus, the overall space complexity of the algorithm is O(n), as it's primarily dependent on the number of buildings to store the balance counter for each building.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫