DAY 29 - Maximum Number of Achievable Transfer Requests

Hey Guys! Nayan here and this is the 29th day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here.

Today we are going to solve the Daily Leetcode question. Although it's tagged as a hard question, It's rather very easy. So Let's get started.

Question: Maximum Number of Achievable Transfer Requests

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] = [fromi, toi] represents an employee's request to transfer from building fromi to building toi.

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. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Examples:

• Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
• Output: 5
• Explantion: Let's see the requests:
• From building 0 we have employees x and y and both want to move to building 1.
• From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
• From building 2 we have employee z and they want to move to building 0.
• From building 3 we have employee c and they want to move to building 4.
• From building 4 we don't have any requests.
• We can achieve the requests of users x and b by swapping their places.
• We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

• Input: n = 3, requests = [[0,0],[1,2],[2,1]]
• Output: 3
• Explantion: Let's see the requests:
• From building 0 we have employee x and they want to stay in the same building 0.
• From building 1 we have employee y and they want to move to building 2.
• From building 2 we have employee z and they want to move to building 1.
• We can achieve all the requests.

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

Constraints:

• 1 <= n <= 20
• 1 <= requests.length <= 16
• requests[i].length == 2
• 0 <= fromi, toi < n

Intuition:

• Let's break down the question first in simpler terms.
• We have n buildings. We also have an array of size N where N is an integer.
• The array contains no of requests for transfer of one employee from one building to another building. It holds building from the employee is going and what its migrating into at it's 0th and 1st index inside requests[i].
• We need to return maximum number of requests that we can agree upon.

So what's the trick. The question is pretty good. Our first thought could be thinking greedy and others.
Well the trick does not lie in the question but rather than the constraints.
Since The requests can be at most 16, we can simply form a recursive brute force solution for this and that should fit well within the constraints.

Another reminder as to why We should never miss constraints.

Approach: Recursion + Backtracking

• Establish Base Case: If we are at the end of our array we will simply return back to our function.
• Create an array for keeping count of total outs and ins in a building. If that is more than 1 return back to the function.
• Our Answer will be max(maxReq, count).
• We are provided two options. Either to accept the request or don't. So we do exactly that.
• Incase we do accept the request, we backtrack into what we had before accepting and use backtracking for not accepting the request.
• Hence we visit every possible solution and return our ans.

Code:

class Solution {
public:
    int maxReq = 0;
    void maxRequests(vector<vector<int>>& requests , vector<int>& changeDegree,int n, int index, int count){
        if(index == requests.size()){
            for(int i =  0; i < n; i++){
                if(changeDegree[i]){
                    return ;
                }
            }
            maxReq = max(maxReq, count);
            return ;
        }
         //two cases approve the request or don't approve
         changeDegree[requests[index][0]]--;
         changeDegree[requests[index][1]]++;
         maxRequests(requests,changeDegree, n, index+1, count+1);
        //don't approve so go back to what we had before
        changeDegree[requests[index][0]]++;
        changeDegree[requests[index][1]]--;
        maxRequests(requests,changeDegree, n, index+1, count);
    }
    int maximumRequests(int n, vector<vector<int>>& requests) {
        int N = requests.size();
        vector<int> changeDegree(n,0);
        maxRequests(requests, changeDegree, n, 0, 0);
        return maxReq;
    }
};

Comeplexity Analysis

Time: O(2^N * n)
Space: O(n). Where N is size of requests and n is the no of buildings.

Thanks for reading. Feedback is highly appreciated.

Note:

• This problem can also be solved using bitmasking with an iterative approach.