1536. Minimum Swaps to Arrange a Binary Grid LeetCode Solution

In this guide, you will get 1536. Minimum Swaps to Arrange a Binary Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Swaps to Arrange a Binary Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Swaps to Arrange a Binary Grid solution in C++
4. Minimum Swaps to Arrange a Binary Grid solution in Java
5. Minimum Swaps to Arrange a Binary Grid solution in Python
6. Additional Resources

Problem Statement of Minimum Swaps to Arrange a Binary Grid

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.
A grid is said to be valid if all the cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.
The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length == grid[i].length
1 <= n <= 200
grid[i][j] is either 0 or 1

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)

1536. Minimum Swaps to Arrange a Binary Grid LeetCode Solution in C++

class Solution {
 public:
  int minSwaps(vector<vector<int>>& grid) {
    const int n = grid.size();
    int ans = 0;
    // suffixZeros[i] := the number of suffix zeros in the i-th row
    vector<int> suffixZeros;

    for (const vector<int> row : grid) {
      const auto itLastOne = find(row.rbegin(), row.rend(), 1);
      const int suffixZeroCount = distance(row.rbegin(), itLastOne);
      suffixZeros.push_back(suffixZeroCount);
    }

    for (int i = 0; i < n; ++i) {
      const int neededZeros = n - 1 - i;
      // Get the first row with suffix zeros >= `neededZeros` in
      // suffixZeros[i:..n).
      const auto it = find_if(suffixZeros.begin() + i, suffixZeros.end(),
                              [&](int count) { return count >= neededZeros; });
      if (it == suffixZeros.end())
        return -1;
      const int j = distance(suffixZeros.begin(), it);
      // Move the rows[j] to the rows[i].
      for (int k = j; k > i; --k)
        suffixZeros[k] = suffixZeros[k - 1];
      ans += j - i;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1536. Minimum Swaps to Arrange a Binary Grid LeetCode Solution in Java

class Solution {
  public int minSwaps(int[][] grid) {
    final int n = grid.length;
    int ans = 0;
    // suffixZeros[i] := the number of suffix zeros in the i-th row
    int[] suffixZeros = new int[n];

    for (int i = 0; i < grid.length; ++i)
      suffixZeros[i] = getSuffixZeroCount(grid[i]);

    for (int i = 0; i < n; ++i) {
      final int neededZeros = n - 1 - i;
      // Get the first row with suffix zeros >= `neededZeros` in suffixZeros[i:..n).
      final int j = getFirstRowWithEnoughZeros(suffixZeros, i, neededZeros);
      if (j == -1)
        return -1;
      // Move the rows[j] to the rows[i].
      for (int k = j; k > i; --k)
        suffixZeros[k] = suffixZeros[k - 1];
      ans += j - i;
    }

    return ans;
  }

  private int getSuffixZeroCount(int[] row) {
    for (int i = row.length - 1; i >= 0; --i)
      if (row[i] == 1)
        return row.length - i - 1;
    return row.length;
  }

  // Returns first row that has suffix zeros > `neededZeros` in suffixZeros[i:..n).
  private int getFirstRowWithEnoughZeros(int[] suffixZeros, int i, int neededZeros) {
    for (int j = i; j < suffixZeros.length; ++j)
      if (suffixZeros[j] >= neededZeros)
        return j;
    return -1;
  }
}
// code provided by PROGIEZ

1536. Minimum Swaps to Arrange a Binary Grid LeetCode Solution in Python

class Solution:
  def minSwaps(self, grid: list[list[int]]) -> int:
    n = len(grid)
    ans = 0
    # suffixZeros[i] := the number of suffix zeros in the i-th row
    suffixZeros = [n if 1 not in row else row[::-1].index(1) for row in grid]

    for i in range(n):
      neededZeros = n - 1 - i
      # Get the first row with suffix zeros >= `neededZeros` in suffixZeros[i:..n).
      j = next((j for j in range(i, n) if suffixZeros[j] >= neededZeros), -1)
      if j == -1:
        return -1
      # Move the rows[j] to the rows[i].
      for k in range(j, i, -1):
        suffixZeros[k] = suffixZeros[k - 1]
      ans += j - i

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.