LeetCode 1536: Minimum Swaps to Arrange a Binary Grid Solution

Master LeetCode problem 1536 (Minimum Swaps to Arrange a Binary Grid), 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.

1536. Minimum Swaps to Arrange a Binary Grid

Medium

Array Greedy Matrix

Problem Explanation

Explanation

To solve this problem, we need to determine the minimum number of swaps required to make the given binary grid valid. A grid is valid if all the cells above the main diagonal (from top-left to bottom-right) are zeros.

We can observe that each row can be represented as a number by considering the binary representation of the row from right to left. The number of trailing zeros in this representation gives us the number of swaps needed to move the row towards the bottom of the grid. If the number of trailing zeros in a row is less than or equal to the number of rows above it, we can swap that row with one of the rows above to move it down.

We can iterate over the rows, calculate the number of trailing zeros for each row, and check if it is possible to swap the row with any of the rows above it. If not, we return -1 since the grid cannot be made valid.

The time complexity of this solution is O(n^2) where n is the size of the grid (number of rows or columns). The space complexity is O(n) to store the trailing zeros for each row.

Solution Code

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        
        // Calculate trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0 && grid[i][j] == 0; j--) {
                count++;
            }
            trailingZeros[i] = count;
        }
        
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int target = n - 1 - i;
            int j = i;
            while (j < n && trailingZeros[j] < target) {
                j++;
            }
            if (j == n) {
                return -1;
            }
            while (j > i) {
                int temp = trailingZeros[j];
                trailingZeros[j] = trailingZeros[j - 1];
                trailingZeros[j - 1] = temp;
                j--;
                swaps++;
            }
        }
        
        return swaps;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1536 (Minimum Swaps to Arrange a Binary Grid)?

This page provides optimized solutions for LeetCode problem 1536 (Minimum Swaps to Arrange a Binary Grid) 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 1536 (Minimum Swaps to Arrange a Binary Grid)?

The time complexity for LeetCode 1536 (Minimum Swaps to Arrange a Binary Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1536 on DevExCode?

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

Back to LeetCode Solutions