Problem Description

You are given a square binary grid, represented as a 2D list grid of size n x n. Each cell contains either a 0 or a 1. You are allowed to swap any two adjacent rows (i.e., swap row i and row i+1 as one move). Your goal is to arrange the grid so that for every row i (0-indexed), all cells in columns right of i (that is, columns i+1 to n-1) are 0. In other words, for each row, all the 1s must be to the left of the diagonal or on the diagonal. You must return the minimum number of swaps needed to achieve this arrangement, or -1 if it is impossible.

• You can only swap adjacent rows.
• Each swap counts as one move.
• Each element can be used multiple times in swaps, but only adjacent rows can be swapped in a single move.
• Return -1 if no valid arrangement is possible.

Thought Process

At first glance, you might consider trying all possible row arrangements, but this would be extremely inefficient for larger grids. Instead, let's focus on what it means for a row to be "valid" at a given position. For row i, all cells to the right of column i must be 0. In other words, the last n - i - 1 elements of row i must be 0. So, for each row, we can count the number of trailing zeros, and for each position i, we need a row with at least n - i - 1 trailing zeros.

Instead of brute-forcing all permutations, we can:

• Compute the number of trailing zeros for each row.
• For each row position, find a suitable row below (or at) that position with enough trailing zeros and move it up using adjacent swaps.
• Count the total swaps needed.

Solution Approach

Let's break down the algorithm step by step:

1. Count Trailing Zeros:
   • For each row in the grid, count the number of zeros at the end of the row (trailing zeros).
   • Store these counts in a list trailing_zeros.
2. Greedy Matching:
   • For each row position i (from top to bottom), determine the minimum number of trailing zeros required: required = n - i - 1.
   • Find the first row at or below position i that has at least required trailing zeros.
   • If no such row exists, it's impossible to arrange the grid; return -1.
   • If found at position j, swap it up to position i (requires j - i swaps).
   • After swapping, update the trailing_zeros list to reflect the new row order.
3. Count Swaps:
   • Keep a running total of all swaps performed.
4. Return the Result:
   • If all rows are successfully placed, return the total swap count.
   • If at any point you cannot find a suitable row, return -1.

This greedy approach works because, for each row, we only need to ensure the constraint is satisfied at that position, and moving a row up does not break the constraints for previous rows.

Example Walkthrough

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

• Step 1: Count trailing zeros for each row:
  • Row 0: [0,0,1] → 0 trailing zeros
  • Row 1: [1,1,0] → 1 trailing zero
  • Row 2: [1,0,0] → 2 trailing zeros
  trailing_zeros = [0,1,2]
• Step 2: For each row position:
  • Position 0: Needs at least 2 trailing zeros. Find first row with ≥2 trailing zeros (row 2). Swap row 2 up to position 0 (2 swaps). trailing_zeros = [2,0,1]
  • Position 1: Needs at least 1 trailing zero. Find first row with ≥1 trailing zero (row 2). Swap row 2 up to position 1 (1 swap). trailing_zeros = [2,1,0]
  • Position 2: Needs at least 0 trailing zeros. Already satisfied.
  Total swaps = 2 + 1 = 3

Output: 3

Each step moves the appropriate row up, and the process is complete when all constraints are satisfied.

Time and Space Complexity

• Brute-force approach:
  • Trying all permutations of rows is O(n!) time, which is infeasible for even moderate n.
• Optimized greedy approach:
  • Counting trailing zeros: O(n^2) (since each row is length n).
  • For each row, searching for a suitable row below: O(n^2) in total (since for each of n rows, we may scan up to n rows below).
  • Total time complexity: O(n^2).
  • Space complexity: O(n) for the trailing_zeros list.

Summary

The key insight is to reduce the problem to counting trailing zeros in each row, and then greedily moving rows with enough trailing zeros up to their required positions using adjacent swaps. This avoids brute-force permutations and ensures an efficient O(n^2) solution. The approach is both simple and effective, leveraging a clear understanding of the grid's constraints.

Code Implementation

class Solution:
    def minSwaps(self, grid):
        n = len(grid)
        trailing_zeros = []
        for row in grid:
            cnt = 0
            for x in reversed(row):
                if x == 0:
                    cnt += 1
                else:
                    break
            trailing_zeros.append(cnt)

        swaps = 0
        for i in range(n):
            required = n - i - 1
            j = i
            while j < n and trailing_zeros[j] < required:
                j += 1
            if j == n:
                return -1
            while j > i:
                trailing_zeros[j], trailing_zeros[j-1] = trailing_zeros[j-1], trailing_zeros[j]
                swaps += 1
                j -= 1
        return swaps
      

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> trailing_zeros(n, 0);
        for(int i = 0; i < n; ++i) {
            int cnt = 0;
            for(int j = n - 1; j >= 0; --j) {
                if(grid[i][j] == 0)
                    cnt++;
                else
                    break;
            }
            trailing_zeros[i] = cnt;
        }
        int swaps = 0;
        for(int i = 0; i < n; ++i) {
            int required = n - i - 1;
            int j = i;
            while(j < n && trailing_zeros[j] < required)
                ++j;
            if(j == n)
                return -1;
            while(j > i) {
                swap(trailing_zeros[j], trailing_zeros[j-1]);
                swaps++;
                j--;
            }
        }
        return swaps;
    }
};
      

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 0)
                    cnt++;
                else
                    break;
            }
            trailingZeros[i] = cnt;
        }
        int swaps = 0;
        for (int i = 0; i < n; ++i) {
            int required = n - i - 1;
            int j = i;
            while (j < n && trailingZeros[j] < required)
                j++;
            if (j == n)
                return -1;
            while (j > i) {
                int tmp = trailingZeros[j];
                trailingZeros[j] = trailingZeros[j - 1];
                trailingZeros[j - 1] = tmp;
                swaps++;
                j--;
            }
        }
        return swaps;
    }
}
      

var minSwaps = function(grid) {
    const n = grid.length;
    let trailingZeros = [];
    for (let i = 0; i < n; ++i) {
        let cnt = 0;
        for (let j = n - 1; j >= 0; --j) {
            if (grid[i][j] === 0)
                cnt++;
            else
                break;
        }
        trailingZeros.push(cnt);
    }
    let swaps = 0;
    for (let i = 0; i < n; ++i) {
        let required = n - i - 1;
        let j = i;
        while (j < n && trailingZeros[j] < required)
            j++;
        if (j === n)
            return -1;
        while (j > i) {
            [trailingZeros[j], trailingZeros[j-1]] = [trailingZeros[j-1], trailingZeros[j]];
            swaps++;
            j--;
        }
    }
    return swaps;
};