Tuesday, March 16, 2021

LeetCode [1151] Minimum Swaps to Group All 1's Together

 1151. Minimum Swaps to Group All 1's Together

Medium

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        int[] dp = new int[n];
        int cnt1 = 0;//number of ones
        int minSwaps = Integer.MAX_VALUE;
        for(int i=0; i<n; ++i){
            if(data[i]==1){
                cnt1++;
                dp[i] = cnt1;
            }
        }
        if(cnt1==0) return 0;

        int l = 0;
        int left1 = 0;
        while(l + cnt1 - 1 < n){
            int swaps = left1 + cnt1 - dp[l+cnt1-1];
            minSwaps = Math.min(minSwaps, swaps);
            left1 +=data[l++];
        }

        return minSwaps;
    }
}

No comments:

Post a Comment