Source: Dev.to

🧱 Beginner‑Friendly Guide: “Minimum Swaps to Arrange a Binary Grid” – Problem 1536

---

Problem Statement

You are given an n × n binary grid (containing only 0s and 1s).
You may swap any two adjacent rows (i.e., rows i and i+1).

Goal:
Find the minimum number of swaps required so that all cells above the main diagonal are 0.
If it is impossible, return -1.

---

Intuition – The Power of Suffix Zeros

A grid is “valid” when:

Instead of moving whole rows around, we can reduce each row to a single number – the count of consecutive zeros at the end of the row (suffix zeros).

The greedy strategy is:

1. For the current row i, compute the required suffix zeros: need = n‑1‑i.
2. Scan downwards from row i to find the first row whose suffix‑zero count ≥ need.
3. “Bubble” that row up to position i using adjacent swaps (exactly foundIdx ‑ i swaps).
4. Repeat for the next row.

If at any step no suitable row exists, the task is impossible (-1).

---

Walkthrough – Example

grid = [[0,0,1],
        [1,1,0],
        [1,0,0]]

1. Pre‑calculation of suffix zeros

suffixZeros = [0, 1, 2]

2. i = 0 – need 2 zeros.
   First row ≥ 2 zeros is at index 2.
   Bubble it up: swap 2↔1, then 1↔0 → 2 swaps.
   suffixZeros becomes [2, 0, 1].

3. i = 1 – need 1 zero.
   First row ≥ 1 zero from index 1 onward is at index 2.
   Bubble it up: swap 2↔1 → 1 swap.
   suffixZeros becomes [2, 1, 0].

Total swaps = 2 + 1 = 3.

---

Reference Implementations

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 auto& row : grid) {
            int cnt = 0;
            for (int j = n - 1; j >= 0 && row[j] == 0; --j) cnt++;
            suffixZeros.push_back(cnt);
        }

        for (int i = 0; i = need) {
                    found = j;
                    break;
                }
            }
            if (found == -1) return -1;

            // Simulate the swaps (bubble up)
            for (int k = found; k > i; --k)
                swap(suffixZeros[k], suffixZeros[k - 1]);

            ans += (found - 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:
            cnt = 0
            for j in range(n - 1, -1, -1):
                if row[j] == 0:
                    cnt += 1
                else:
                    break
            suffix_zeros.append(cnt)

        ans = 0
        for i in range(n):
            need = n - 1 - i
            found = -1

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

            if found == -1:
                return -1

            # Move the row to position i (simulates adjacent swaps)
            row_to_move = suffix_zeros.pop(found)
            suffix_zeros.insert(i, row_to_move)
            ans += (found - 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 cnt = 0;
        for (let j = n - 1; j >= 0; j--) {
            if (row[j] === 0) cnt++;
            else break;
        }
        suffixZeros.push(cnt);
    }

    let ans = 0;
    for (let i = 0; i = need) {
                found = j;
                break;
            }
        }
        if (found === -1) return -1;

        // Move the required value to the current position (bubble up)
        const val = suffixZeros.splice(found, 1)[0];
        suffixZeros.splice(i, 0, val);
        ans += (found - i);
    }
    return ans;
};

---

Key Takeaways

• Greedy is optimal – always pick the first row that satisfies the current requirement; this leaves the most flexibility for later rows.
• Data reduction – converting each row to a single “suffix‑zero” count turns a 2‑D problem into a simple 1‑D array manipulation.
• Swap cost – moving an element from index j to index i via adjacent swaps costs exactly j ‑ i swaps.

---

Final Thoughts

This problem illustrates a powerful pattern: focus on row‑level properties rather than individual cells when dealing with grid constraints. By reducing the problem to a 1‑D greedy selection, we obtain a clean, O(n²) solution that is easy to implement in any language. Happy coding!

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.