Leetcode 2134: Minimum Swaps to Group All 1’s Together II

In this exercise, we try to put all the ones together in a circular array by swapping elements. We need to find the minimum number of swaps needed:

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.

We are given some examples to test:

Examples and constraints

To solve this problem, the trick is not to do any of the swaps, but to instead find the window for which we need the minimum number of swaps.

Let n by the number of 1s in the circular array. We need to find the best possible window of size n. For a window of size n with p 1s in it, we would need n — p swaps for the n — p 1s that are not currently in the window. Which window should we pick then? We should pick the window with maximal p, which is the window that has the maximum number of ones.

We derive then the following algorithm:

1. Count the number of 1s: count
2. Get the window with maximum number of 1s: max
3. Return count — max.