Understanding a particular solution to 'Minimum Swaps to Group All 1's Together 2nd'-CodePudding

I am looking at the LeetCode problem 2134. Minimum Swaps to Group All 1's Together II:

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

I am trying to study how other people came up with solutions of their own. I came across this particular one, but I don't understand the logic:

class Solution {
    public int minSwaps(int[] nums) {
        // number of ones    
        int cntones=Arrays.stream(nums).sum();
        // worst case answer
        int rslt=nums.length;
        // position lft and figure better value for min/rslt
        int holes = 0;
        for(int i=0;i<cntones;i  ) {
            if(nums[i]==0)
                holes  ;
        }
        // better value for rslt from lft to rgt
        // up to index of cntones.
        rslt = Math.min(rslt, holes);
        
        // they have a test case with one element 
        // and that trips up if you dont do modulo
        int rgt=cntones % nums.length;
        for(int lft=0;lft<nums.length;lft  ) {
            rslt=Math.min(rslt,holes);
            if(nums[lft]!=nums[rgt]) 
                if(nums[rgt]==1)
                    holes--;
                else 
                    holes  ;
            rgt=(rgt 1)%nums.length;
        }
        return rslt;
    }
}

Why is the worst case, the length of the input array? I'm thinking wait, wouldn't the worst case be something like [0,1,0,1,0,1...] where 0's and 1's are alternating? Can you give me an example?
I suppose #of holes can potentially be a possible solution in some cases, from counting 0's in a fixed length (the number of total 1's) of a window but because I do not understand the worst case, rslt from question #1, below line stumps me as well.
```
// better value for rslt from lft to rgt
// up to index of cntones.
rslt = Math.min(rslt, holes);
```
About the modulo below, I don't think cntones can ever be bigger than nums.length, in turn which will result in 0 all the time? I'm thinking for the case with one element, you'd have to check whether that one element is 0 or 1. How does below line cover that edge case?
```
// they have a test case with one element 
// and that trips up if you dont do modulo
int rgt=cntones % nums.length; 
```
Due to #1~#3 the last for loop makes no sense to me...

CodePudding user response：

Why is the worst case, the length of the input array?

First note that a swap is only useful when it swaps a 0 with 1. Secondly, it makes no sense to swap the same digit a second time, as the result of such double swap could have been achieved with a single swap. So we can say that an upper limit for the number of swaps is the number of 0-digits or number of 1-digits (which ever is the least). In fact, this is an overestimation, because at least one 1-digit should be able to stay unmoved. But let's ignore that for now. To reach that worst case, there should be as many 1 as 0 digits, so then we have half of the length as worst case. Of course, by initialising with a value that is greater than that (like the length) we do no harm.

The example of alternating digits would be resolved by keeping half of those 1-digits unmoved, and moving the remaining 1-digits in the holes between them. So that means we have a number of swaps that is equal to about one fourth of the length of the array.

below line stumps me as well.
rslt = Math.min(rslt, holes);

As you said, there is a window moving over the circular array, which represents the final situation where all 1-digits should end up. So it sets the target to work towards. Obviously, the 1-digits that are already within that window don't need to be swapped. Each 0-digit inside that window has to be swapped with a 1-digit that is currently outside that window. Doing that will reach the target, and so the number of swaps for reaching that particular target window is equal to the number of holes (0-digits) inside that window.

As that exercise is done for each possible window, we are interested to find the best position of the window, i.e. the one where the number of holes (swaps) is minimised. That is what this line of code is doing. rslt is the minimum "so far" and holes is the fresh value we have for the current window. If that is less, then rslt should be updated to it. That's what happens in this statement.

About the modulo below, I don't think cntones can ever be bigger than nums.length, in turn which will result in 0 all the time? I'm thinking for the case with one element, you'd have to check whether that one element is 0 or 1. How does below line cover that edge case?
int rgt=cntones % nums.length; 

That modulo only serves for the case that cntones is equal to nums.length. You are right that it will never exceed it. But the case where it is equal is possible (when the input only has 1-digits). And as rgt is going to be used as an index, it should not be equal to nums.length as that is an undefined slot in the array.

Due to #1~#3 the last for loop makes no sense to me...

It should be clear from the above details. That loop moves the window with one step at a time, and keeps the variable holes updated incrementally. Of course, we could have decided to count the number of holes from scratch in each window, but that would be a waste of time. As we go from one window to the next, we only lose one digit on the left and gain one on the right, so we can just update holes with that information and know how many holes there are in the current window -- the one that starts at lft and runs (circular) to rgt. In case the digit that we lose at the left is the same as the one we gain at the right, we obviously didn't change the number of holes. Where they are different, we either win or lose one hole in comparison with the previous window.