LC: 1151. Minimum Swaps to Group All 1's Together - spiralgo/algorithms GitHub Wiki

1151. Minimum Swaps to Group All 1's Together

The Essence:

In the given array, all 1's must be grouped together. This is logically equivalent to saying that all 1's should be located in a given window in the array, length of which is the number of 1's in the array. The minimum swaps is then the number of 0's in this window.

As an example:

We count that there are 5 1's in some array. Let there be some window starting at some index: [1, 1, 0, 0, 1]. This means that we need to swap out the 2 0's in order to have only 1's in this window, and hence all the 1's together. With this procedure, we check all the windows in the array and return the least amount of 0's that is counted in any of these windows.

Details:

In a first loop, the number of 1's can be counted. The number of 0's in each window can be checked using prefix sums or comparing new and leaving values with the current total sum.