1151. Minimum Swaps to Group All 1's Together

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

 

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: 
There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: 
Since there is only one 1 in the array, no swaps needed.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: 
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Example 4:

Input: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
Output: 8

 

Constraints:

  • 1 <= data.length <= 105
  • data[i] is 0 or 1.

Rust Solution

struct Solution;

impl Solution {
    fn min_swaps(data: Vec<i32>) -> i32 {
        let n = data.len();
        let m = data.iter().sum::<i32>() as usize;
        let mut sum = 0;
        let mut max_sum = 0;
        for i in 0..n {
            if i < m {
                sum += data[i];
            } else {
                sum += data[i];
                sum -= data[i - m];
            }
            max_sum = max_sum.max(sum);
        }

        m as i32 - max_sum
    }
}

#[test]
fn test() {
    let data = vec![1, 0, 1, 0, 1];
    let res = 1;
    assert_eq!(Solution::min_swaps(data), res);
    let data = vec![0, 0, 0, 1, 0];
    let res = 0;
    assert_eq!(Solution::min_swaps(data), res);
    let data = vec![1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1];
    let res = 3;
    assert_eq!(Solution::min_swaps(data), res);
}

Having problems with this solution? Click here to submit an issue on github.