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
class Solution {
public int minSwaps(int[][] grid) {
int[] trailingZero=new int[grid.length];
for(int i=0;i<grid.length;i++){
for(int j=grid.length-1;j>=0;j--){
if(grid[i][j]==0) trailingZero[i]++;
else break;
}
}
int n=trailingZero.length;
int swap=0;
for(int i=0;i<n;i++){
int requiredIndex=n-i-1; //How many zeros do we need at ith index
for(int j=i;j<n;j++){
if(trailingZero[j]>=requiredIndex){ // we have found the row we should swap with
for(int k=j;k>i;k--){ //keep swapping adjacent rows until we reach ith row
swap++;
int temp = trailingZero[k];
trailingZero[k]=trailingZero[k-1];
trailingZero[k-1]=temp;
}
break;
}
if(j==n-1) return -1;
}
}
return swap;
}
}