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

Difficulty: interview

Starter code:

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        start=1
        swap=0
        n=len(grid)
        zeros_ingrid=n-1
        while zeros_ingrid>0:
            swapped_grid=False
            for i in range(len(grid)):
                if sum(grid[i][start:])==0:
                    swap+=i
                    grid.remove(grid[i])
                    swapped_grid=True
                    zeros_ingrid-=1
                    start+=1
                    break
            if not swapped_grid:
                return -1
        return swap
                
                    
                
                


class Solution:
  dbg = False
  def minSwaps(self, grid) -> int:
    grid_ints = []
    for row in grid:
      enc = 0
      for val in reversed(row):
        enc = enc << 1
        if val % 2 == 1:
          enc += 1
      grid_ints.append(enc)
    if self.dbg: print(grid_ints)

    bar = 1
    swaps = 0
    for i in range(len(grid[0])):
      if grid_ints[i] > bar:
        j = i
        while grid_ints[j] > bar:
          j += 1
          if j >= len(grid[0]):
            return -1
        while j > i:
          grid_ints[j], grid_ints[j-1] = grid_ints[j-1], grid_ints[j]
          swaps += 1
          j -= 1
      bar = (bar << 1) + 1

    return swaps


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

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        def helper(row):
            for i in range(len(row) - 1, -1, -1):
                if row[i] == 1:
                    return len(row) - i - 1
            return len(row)
        arr = list(map(helper, grid))

        count = 0
        target = len(grid[0]) - 1
        for i in range(len(arr)):
            if arr[i] < target:
                found = False
                for j in range(i + 1, len(arr)):
                    if arr[j] >= target:
                        count += j - i
                        arr.insert(i, arr.pop(j))
                        found = True
                        break
                if not found:
                    return -1
            target -= 1
            
        return count

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:
        n = len(grid[0])
        def countzeros(row):
            zeros = 0
            while(row):
                new=row.pop()
                if new ==0:
                    zeros +=1
                else:
                    return(zeros)
            return(zeros)
        zeros = [countzeros(i) for i in grid]
        print(zeros)
        row = 0 #n-1 zeros need, for row = k need n-1-k zeros
        ops = 0
        while(len(zeros)):
            #print(zeros)
            found = False
            for i in range(len(zeros)):
                if zeros[i] >= n - 1 -row:
                    ops += i 
                    zeros.remove(zeros[i])
                    row +=1
                    found = True
                    break
            if not found:
                return(-1)
        return(ops)