Minimum Swaps to Arrange a Binary Grid

LeetCode 1536 looks like a matrix manipulation problem — but it’s actually a greedy row placement problem. Once you understand the core idea, the solution becomes simple.

---

📌 Problem Summary

You are given an n × n binary grid.

• You can swap adjacent rows only.
• Your goal is to rearrange rows so that for every row i, all elements above the main diagonal are 0.

If it is impossible, return -1.

---

🧠 Key Insight

We don’t care about the full row. We only care about:

👉 Number of trailing zeros in each row

Because the diagonal condition means:

Row 0 → needs at least (n-1) trailing zeros
Row 1 → needs at least (n-2) trailing zeros
Row 2 → needs at least (n-3) trailing zeros
...

---

📌 Example

Input:
[
 [0,0,1],
 [1,1,0],
 [1,0,0]
]

Step 1: Count Trailing Zeros

Row 0 → 1 trailing zero
Row 1 → 1 trailing zero
Row 2 → 2 trailing zeros

Convert to array:

[1, 1, 2]

---

Step 2: Required Zeros Per Position

For n = 3:

Row 0 needs ≥ 2
Row 1 needs ≥ 1
Row 2 needs ≥ 0

---

🔁 Step-by-Step Swapping

Position 0 needs ≥ 2 zeros.

Index 0 → 1 ❌
Index 1 → 1 ❌
Index 2 → 2 ✅

Bubble row at index 2 upward:

[1, 1, 2]
Swap → [1, 2, 1]
Swap → [2, 1, 1]

Swaps = 2

Remaining rows already satisfy condition.

Final Answer = 2

---

🔥 Why Greedy Works

• Top rows require the most trailing zeros.
• We must place the earliest valid row immediately.
• If we delay, we may lose feasibility.

This is essentially:

Greedy row placement + bubble swaps

---

💻 Java Implementation

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];

        // Count trailing zeros
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) count++;
                else break;
            }
            trailingZeros[i] = count;
        }

        int swaps = 0;

        for (int i = 0; i < n; i++) {
            int required = n - 1 - i;
            int j = i;

            while (j < n && trailingZeros[j] < required) {
                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;
    }
}

---

⏱ Complexity Analysis

• Counting trailing zeros → O(n²)
• Bubble swaps (worst case) → O(n²)

Total Time Complexity: O(n²)

---

⚠️ Common Mistakes

• Trying to swap columns ❌
• Thinking diagonal must be 1 ❌
• Using dynamic programming ❌

Remember: This is NOT a matrix problem. It is a greedy placement problem.

---

📌 Final Takeaway

When solving grid problems:

• Identify the property that matters.
• Ignore unnecessary details.
• Reduce the problem to a simpler structure.

Here, everything reduces to:

Trailing Zeros + Greedy Row Placement

---