1151. Minimum Swaps to Group All 1's Together

• Number of swaps = totalones - maximum number of ones in a window of size ones

T: O(n)
S: O(1)

class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        int winSize = 0;
        for (int num : data) {
            if (num == 1) {
                winSize++;
            }
        }
        
        int oneCount = 0;
        int left = 0;
        int res = winSize;
        
        for (int right = 0; right < n; right++) {
            if (right - left + 1 > winSize) {
                oneCount -= data[left++];
            }
            oneCount += data[right];
            
            if (right - left + 1 == winSize) {
                res = Math.min(res, winSize - oneCount);
            }
        }
        return res;
    }
}
/*
min swap = total of one's count(win size) - one's count in this sliding window
 0 1 2
[1,0,1,0,1]
[     ]

T: O(n)
S: O(1)
*/

or count 0

class Solution {
    public int minSwaps(int[] data) {
        int winSize = 0;
        for (int d : data) {
            if (d == 1) {
                winSize++;
            }
        }
        if (winSize == 1) {
            return 0;
        }
        
        int res = Integer.MAX_VALUE;
        int minSwaps = 0;
        int left = 0;
        for (int right = 0; right < data.length; right++) {
            if (data[right] == 0) {
                minSwaps++; 
            }
            if (right - left + 1 > winSize) {
                if (data[left] == 0) {
                    minSwaps--;
                }
                left++;
            }
            if (right - left + 1 == winSize) {
                res = Math.min(res, minSwaps); 
            }
        }
        return res;
    }
}

/*
we know there are 3 ones, so use a sliding window size = 3 to parse
0 1. 2.3
[1,0,1,0,1]
[     ]
   [    ]
     [    ]  Minimum Swaps is 1
     in these sliding win Minimum num of 0 is 1
     
     
[1,0,1,0,1,0,0,1,1,0,1]     , win size = 6
[           ]
  [           ]
     [           ]
       [           ]
         [           ] 
*/