Leetcode 1601. Maximum Number of Achievable Transfer Requests

Question

I am trying to solve LeetCode problem 1601. 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] = [fromᵢ, toᵢ] represents an employee's request to transfer from building fromᵢ to building toᵢ.

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.

Below is my attempt:

class Solution {
    public int maximumRequests(int n, int[][] requests) {
        int[] out= new int[n]; // count outgoing for each building
        int[] in= new int[n]; // count incoming for each building

        for(int i=0;i<requests.length;i++){
            int x=requests[i][0];
            int y=requests[i][1];
            out[x]++;
            in[y]++;
        }

        int ans=0;
        for(int i=0;i<n;i++){
            // Achievable transfer happens only when net is ZERO
            //    so min of in & out can be achieved
            ans+=Math.min(in[i],out[i]); 
        }

        return ans;
    }
}

Why doesn't the above code work? On further analysis I found that I don't even understand the below example Input/output:

Input:

3
[[2,2],[2,1],[1,0]]

Expected Output:

1

Both requests [2,2],[2,1] can be accepted only if 1 employee leaves building# 1, which is possible as there's a request [1,0]. But for [1,0] to be possible someone should leave building# 0, which is not happening. According to the problem statement initially all buildings are full, so how come one employee goes out from 1 to 0 without someone coming out from 0?

I found someone's backtracking solution, but why is backtracking needed? Why doesn't the above solution work and how does the above example input/output work?

Answer 1

I don't even understand the below example Input/output:

3
[[2,2],[2,1],[1,0]]

Expected output:

1

how come one employee goes out from 1 to 0 without someone coming out from 0?

Indeed that is not a possible move, and it is not counted either:

• [2,2]: possible, the person moves out and in to the same building, coming back to the spot they left.
• [1,0]: not possible, for the reason you gave
• [2,1]: not possible, because the move [1,0] is not possible.

So the total number of moves that are possible is 1.

Why doesn't the above code work?

Because with Math.min(in[i],out[i]) you are not sure yet that all these remaining moves are actually possible. For instance, if we apply that to the above problem at index 1, then Math.min(in[1],out[1]) is Math.min(1,1) is 1, but this is too optimistic, because that "out" (i.e. [1,0]) is not going to happen.

why is backtracking needed?

Because you cannot know what the number of possible moves is at a certain building without looking at the situation at the other buildings (to which and from which persons want to move). And once you have looked there and diminished the number of possible moves for the current building accordingly, this information has to flow back to previously visited buildings, to also adapt their move-counts, as those may depend on the current building.