LeetCode 1151: Minimum Swaps to Group All 1's Together Solution

Master LeetCode problem 1151 (Minimum Swaps to Group All 1's Together), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1151. Minimum Swaps to Group All 1's Together

Medium

Array Sliding Window

Problem Explanation

Explanation:

The problem asks us to find the minimum number of swaps required to group all 1's together in a binary array. We can solve this problem by using the sliding window technique.

First, we calculate the total number of ones in the input array.
We then create a window of size equal to the number of ones in the array and move it through the input array to find the window with the maximum number of ones.
The minimum number of swaps required will be the difference between the number of ones in the window with the maximum number of ones and the total number of ones in the array.

Algorithm:

Calculate the total number of ones in the input array.
Create a window of size equal to the number of ones in the array.
Initialize a variable maxOnes to keep track of the maximum number of ones in a window.
Traverse through the array and count the number of ones in the first window.
Update maxOnes with this count.
Slide the window through the array and update maxOnes if we find a window with more ones.
The minimum swaps required will be the difference between the number of ones in the window with maxOnes and the total number of ones in the array.

Time Complexity: O(n) where n is the length of the input array. Space Complexity: O(1)

Solution Code

class Solution {
    public int minSwaps(int[] data) {
        int onesCount = 0;
        for (int num : data) {
            onesCount += num;
        }
        
        int windowOnes = 0;
        for (int i = 0; i < onesCount; i++) {
            windowOnes += data[i];
        }
        
        int maxOnes = windowOnes;
        for (int i = onesCount; i < data.length; i++) {
            windowOnes += data[i] - data[i - onesCount];
            maxOnes = Math.max(maxOnes, windowOnes);
        }
        
        return onesCount - maxOnes;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1151 (Minimum Swaps to Group All 1's Together)?

This page provides optimized solutions for LeetCode problem 1151 (Minimum Swaps to Group All 1's Together) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1151 (Minimum Swaps to Group All 1's Together)?

The time complexity for LeetCode 1151 (Minimum Swaps to Group All 1's Together) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1151 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1151 in Java, C++, or Python.

Back to LeetCode Solutions