1

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?

1
  • This lacks a minimal reproducible example and a clear problem description or question. There's too many problems and parts of the description are on some external, volatile site. Commented Jul 2, 2023 at 16:08

1 Answer 1

0

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.

Sign up to request clarification or add additional context in comments.

2 Comments

So that means all moves of the type [i,i] will be valid because the person can always come back to the original spot. Is it?
Yes, that is correct.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.