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
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

Solution:

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        
        // count the number of consecutive zeros from end of each rows
        // [[0,0,1],[1,1,0],[1,0,0]] - > [0, 1, 2]
        int[] count = new int[n];
        for (int i = 0; i < n; i ++) {
            int[] row = grid[i];
            for (int j = n - 1; j >= 0; j --) {
                if (row[j] == 0) {
                    count[i] ++;
                } else {
                    break;
                }
            }
        }
        
        // System.out.println(Arrays.toString(count));
                
        int swap = 0;
        for (int i = 0; i < n; i ++) {
            boolean found = false;
            // for each row, we need at least n - i - 1 zeros
            int minZeros = n - i - 1;
            if (count[i] < minZeros) {
                // find the first row that has n - i - 1 zeros, and swap with it
                // The reason why greedy approach works is that arr will be in "descending" order after rearrangement, so it's fine to push smaller numbers downwards.
                // Here the "descending" order is not strict. arr is good as long as arr[i] >= n - i - 1. For example, arr = [4,3,4,4] is valid.
                // the requirement of arr[i] keeps decreasing
               for (int j = i + 1; j < n; j ++) {
                    if (count[j] >= minZeros)  {
                        found = true;
                        swap += j - i;
                        while (j > i) {
                            swap(count, j, j - 1);
                            j --;
                        }
                        break;
                    }
                }
                if (!found) { 
                    return -1;
                }
            }
        }
        
        return swap;
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}