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).

&nbsp;
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


&nbsp;
Constraints:


	n == grid.length == grid[i].length
	1 &lt;= n &lt;= 200
	grid[i][j] is either 0 or 1


class Solution:
    def minSwaps(self, grid) -> int:
        n = len(grid)
        max_right = [-1] * n
        for r, row in enumerate(grid):
            for c in range(n - 1, -1, -1):
                if row[c] == 1:
                    max_right[r] = c
                    break
        if all(v <= i for i, v in enumerate(sorted(max_right))):
            swaps = 0
            i = 0
            while i < n:
                while i < n and max_right[i] <= i:
                    i += 1
                if i == n:
                    break
                j = i
                while j < n and max_right[j] > i:
                    j += 1
                swaps += j - i
                max_right[i], max_right[i + 1: j + 1] = (max_right[j],
                                                         max_right[i: j])
                i += 1
            return swaps
        return -1
class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length, ans = 0, cur = 0;
        for (int k = 0; k < n - 1; k++){ // looking for the fitting row for row k
            for (int i = k; i < n; i++){ // start from row k looking downward
                for (int j = k + 1; j < n; j++){ // all cell after and at k + 1 must be 0
                    if (grid[i][j] == 1)
                        break;
                    if (j < n - 1)
                        continue;
                    for (int m = i; m > k; m--){ // j == n - 1 here, so we found a valid row
                        int[] tmp = grid[m - 1];  // swap it into the correct row - row k
                        grid[m - 1] = grid[m];
                        grid[m] = tmp;
                        ans++;
                    }
                    i = n;
                }
                if (i == n - 1) // i reaches the end and did not find a fitting row, return -1
                    return -1;
            }
        }
        return ans;
    }
}
class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {

        int n = grid.size();
        vector<int> mr(n,0);
        vector<int> br(n,0);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                    mr[i] = j;
            }
        }
        br = mr;
        sort(mr.begin(),mr.end());
        for(int i=0;i<n;i++)
            if(mr[i]>i)
                return -1;
        int count = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(br[i]>i){
                    swap(br[i],br[j]);
                    count++;
                }
            }
        }
        return count;
    }
};
var minSwaps = function(grid) {
    const arr = [];
    let count = 0;

    for(let row of grid) {
        arr.push(row.lastIndexOf(1));
    }

    function swap(i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        count++;
    }

    for(let i = 0; i < arr.length; i++) {
        // if num <= i pass b/c it's its correct spot
        if(arr[i] <= i) continue;
        let j = i;

        // scan forward looking for a num <= i
        while(arr[j] > i) {
            j++;
            if(j >= arr.length) return -1;
        }

        // swap as you move back to the right spot
        for(let k = j; k > i; k--) {
            swap(k, k-1);
        }
    }
    return count;
};
Minimum Swaps to Arrange a Binary Grid