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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Greedy algorithms

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
		ops = 0
		while len(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