1601. Maximum Number of Achievable Transfer Requests
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.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
-
Is it a graph?
- No: The problem does not involve graph-based relationships like nodes directly connected by edges. It's more about requests and state changes.
-
Need to solve for kth smallest/largest?
- No: The problem is about maximizing the number of achievable requests, not finding an order-based kth element.
-
Involves Linked Lists?
- No: This problem does not involve linear data structures like linked lists.
-
Does the problem have small constraints?
- Yes: The constraints on the number of requests and buildings are typically small enough to consider trying all combinations, which makes brute force or backtracking feasible.
-
Brute force / Backtracking?
- Yes: Given the problem's nature of permutations and combinations of requests that can be granted under certain constraints, backtracking is ideal to explore all possible configurations to maximize the achievability.
Conclusion: The flowchart suggests using the backtracking approach to try different combinations of transfer requests and find the maximum number that can be achieved given the constraints.
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.
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:
-
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 sizen
, 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 thecnt
array by decrementing the count for thefrom
building and incrementing it for theto
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.
-
Initialize a variable
ans
with0
to keep track of the maximum number of achievable requests found. -
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.
- The range of the loop is
-
Inside the loop, calculate the number of requests included in the current subset using
mask.bit_count()
, which returns the number of set bits (or1
s) in the bitmask. -
If the current mask has more requests than
ans
(the previous maximum), and thecheck(mask)
function confirms that the current subset is achievable, updateans
with the count of the current subset. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Initialize Maximum Achievable Requests (
ans
):We start by setting
ans
to0
, as we have not processed any requests yet. -
Iterate Through All Possible Subsets:
With
4
requests, there are2^4 = 16
possible combinations of these requests, from no requests (bitmask0000
) to all requests (bitmask1111
). -
Evaluate Each Subset (Bitmask):
For each bitmask, we perform the following steps:
- Bitmask
0000
: No requests are included, thusans
remains0
. - Bitmask
0001
: The subset includes just the last request[2, 0]
. This is achievable as we can transfer one employee from building2
to0
. - Bitmask
0010
: The subset includes the request[0, 2]
. This is also achievable in isolation, butans
remains at1
because we already found a subset of1
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 be0
, so the subset is achievable. Since this subset has3
transfers,ans
is updated to3
.
- Bitmask
-
Check Each Subset For Balance (Using
check
Function):When we evaluate each set, the
check
function will update an arraycnt
that tracks the net change in number of employees at each building, considering which requests are included in the current subset. If all entries incnt
are0
, it means that the current subset of requests is balanced and thus achievable. -
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 is3
, 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
Time and Space Complexity
Time Complexity
The time complexity of the code is primarily determined by two nested operations:
-
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 are2^(len(requests))
possible subsets, resulting in a time complexity ofO(2^m)
for this loop, wherem
is the length ofrequests
. -
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 ofO(m + n)
, wheren
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:
-
The counter array
cnt
for building balances, which usesO(n)
space, wheren
is the number of buildings. -
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.
Which of the following uses divide and conquer strategy?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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