🧱 Beginner-Friendly Guide 'Minimum Swaps to Arrange a Binary Grid' - Problem 1536 (C++, Python, JavaScript)

Sorting a grid might seem like a complex task, but it often boils down to identifying a single critical property of each row. In this challenge, we explore how to transform a matrix through greedy swaps to satisfy a specific geometric constraint.
You're given:

• An n \times n binary grid consisting of 0s and 1s.
• The ability to swap any two adjacent rows. Your goal:
• Find the minimum number of swaps needed so that all cells above the main diagonal are zeros.
• Return -1 if it is impossible to reach this state. Intuition: The Power of Suffix Zeros To make a grid "valid," the first row must have at least n - 1 zeros at the end. The second row needs at least n - 2 zeros, and so on. The last row doesn't require any trailing zeros. Instead of moving the whole grid, we can simplify each row into a single number: the count of consecutive zeros starting from the right (suffix zeros). The strategy is Greedy:
• For the current row i, determine how many suffix zeros are required (n - 1 - i).
• Search downward from the current row to find the first row that satisfies this requirement.
• Once found, "bubble" that row up to the current position using adjacent swaps. This is similar to a single pass of Bubble Sort.
• If no such row exists in the remaining options, the task is impossible. Walkthrough: Understanding the Examples Example 1: grid = [0,0,1],[1,1,0],[1,0,0]
• Step 0 (Pre-calculation):
  • Row 0: [0,0,1] has 0 suffix zeros.
  • Row 1: [1,1,0] has 1 suffix zero.
  • Row 2: [1,0,0] has 2 suffix zeros.
  • suffixZeros array: [0, 1, 2]
• Step 1 (Row i = 0): Needs 3 - 1 - 0 = 2 zeros. The first row with \ge 2 zeros is at index 2. Swap index 2 with 1, then index 1 with 0. (2 swaps). Array becomes [2, 0, 1].
• Step 2 (Row i = 1): Needs 3 - 1 - 1 = 1 zero. The first row from index 1 onwards with \ge 1 zero is at index 2. Swap index 2 with 1. (1 swap). Array becomes [2, 1, 0].

• Total Swaps: 2 + 1 = 3.
  Code Blocks
  C++
  class Solution {
  public:
  int minSwaps(vector>& grid) {
  const int n = grid.size();
  int ans = 0;
  vector suffixZeros;

  // Pre-calculate suffix zeros for each row
  for (const vector& row : grid) {
  int count = 0;
  for (int j = n - 1; j >= 0 && row[j] == 0; --j) {
  count++;
  }
  suffixZeros.push_back(count);
  }

  for (int i = 0; i < n; ++i) {
  const int neededZeros = n - 1 - i;
  int foundIdx = -1;

  // Find the first row that satisfies the requirement
  for (int j = i; j < n; ++j) {
  if (suffixZeros[j] >= neededZeros) {
  foundIdx = j;
  break;
  }
  }

  if (foundIdx == -1) return -1;

  // Simulate the swaps and accumulate the cost
  for (int k = foundIdx; k > i; --k) {
  swap(suffixZeros[k], suffixZeros[k - 1]);
  }
  ans += (foundIdx - i);
  }

  return ans;
  }
  };

Python
class Solution:
def minSwaps(self, grid: list[list[int]]) -> int:
n = len(grid)
suffix_zeros = []

    # Pre-calculate suffix zeros for each row
    for row in grid:
        count = 0
        for j in range(n - 1, -1, -1):
            if row[j] == 0:
                count += 1
            else:
                break
        suffix_zeros.append(count)

    ans = 0
    for i in range(n):
        needed_zeros = n - 1 - i
        found_idx = -1

        # Find the first row meeting the criteria
        for j in range(i, n):
            if suffix_zeros[j] >= needed_zeros:
                found_idx = j
                break

        if found_idx == -1:
            return -1

        # Move the row to current position i
        # Using pop and insert simulates the adjacent swaps efficiently
        row_to_move = suffix_zeros.pop(found_idx)
        suffix_zeros.insert(i, row_to_move)
        ans += (found_idx - i)

    return ans

JavaScript
/**

• @param {number[][]} grid

• @return {number}
  */
  var minSwaps = function(grid) {
  const n = grid.length;
  const suffixZeros = [];

  // Pre-calculate suffix zeros for each row
  for (const row of grid) {
  let count = 0;
  for (let j = n - 1; j >= 0; j--) {
  if (row[j] === 0) {
  count++;
  } else {
  break;
  }
  }
  suffixZeros.push (count);
  }

  let ans = 0;
  for (let i = 0; i < n; i++) {
  const neededZeros = n - 1 - i;
  let foundIdx = -1;

  for (let j = i; j < n; j++) {
      if (suffixZeros[j] >= neededZeros) {
          foundIdx = j;
          break;
      }
  }
  
  if (foundIdx === -1) return -1;
  
  // Move the required value to the current position
  const val = suffixZeros.splice(foundIdx, 1)[0];
  suffixZeros.splice(i, 0, val);
  ans += (foundIdx - i);
  

  }

  return ans;
  };

Key Takeaways

• Greedy Strategy: Choosing the first available row that meets the criteria is optimal because it leaves the most flexible options for subsequent rows.
• Data Reduction: Reducing a complex 2D grid into a 1D array of counts makes the problem much easier to reason about.
• Simulation Cost: The number of swaps needed to move an element from index j to index i is exactly j - i. Final Thoughts This problem is a classic example of how to handle constraints in a grid by focusing on the properties of rows rather than the individual cells. In real-world software engineering, this kind of logic is frequently applied in resource scheduling or data packet ordering, where you need to arrange items to meet specific priority thresholds with minimal overhead. Mastering greedy simulations is a key step toward passing technical interviews for roles in systems optimization.