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:
    def minSwaps(self, grid: List[List[int]]) -> int:
        maxRight = [0]* len(grid)
        
        for i in range(len(grid)):
            j = len(grid[i]) - 1
            while j >= 0 and grid[i][j] != 1:
                j -= 1
            maxRight[i] = j
            
       
            
        swaps = 0
        for i in range(len(maxRight)):
            if maxRight[i] > i:
                j = i
                while j < len(maxRight) and maxRight[j] > i:
                    j += 1
                    
                if j == len(maxRight):
                    return -1
                
                while j != i:
                    temp = maxRight[j]
                    maxRight[j] = maxRight[j-1]
                    maxRight[j-1] = temp
                    swaps += 1
                    j -= 1
            

        return swaps
            
                
            
            
            

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        maxRight = [0]* len(grid)
        
        for i in range(len(grid)):
            j = len(grid[i]) - 1
            while j >= 0 and grid[i][j] != 1:
                j -= 1
            maxRight[i] = j
            
       
            
        swaps = 0
        for i in range(len(maxRight)):
            if maxRight[i] > i:
                j = i
                while j < len(maxRight) and maxRight[j] > i:
                    j += 1
                    
                if j == len(maxRight):
                    return -1
                
                while j != i:
                    temp = maxRight[j]
                    maxRight[j] = maxRight[j-1]
                    maxRight[j-1] = temp
                    swaps += 1
                    j -= 1
            

        return swaps
            
                
            
            
            
