<p>Given an <code>n x n</code> binary <code>grid</code>, in one step you can choose two <strong>adjacent rows</strong> of the grid and swap them.</p>

<p>A grid is said to be <strong>valid</strong> if all the cells above the main diagonal are <strong>zeros</strong>.</p>

<p>Return <em>the minimum number of steps</em> needed to make the grid valid, or <strong>-1</strong> if the grid cannot be valid.</p>

<p>The main diagonal of a grid is the diagonal that starts at cell <code>(1, 1)</code> and ends at cell <code>(n, n)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/28/fw.jpg" style="width: 750px; height: 141px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,1],[1,1,0],[1,0,0]]
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/16/e2.jpg" style="width: 270px; height: 270px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> All rows are similar, swaps have no effect on the grid.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/16/e3.jpg" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0],[1,1,0],[1,1,1]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code> <code>== grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code></li>
</ul>

class Solution:
    # rows below main diagonal dont matter
    # only swap adj rows
    # check if possible. easy linear check
    # need a row with at least n-1 0's in top right
    # .... at least n-2 0's...
    # at least 0 0 ...

    # try greedy swapping? ex. start from bottom, (or top) and swap for the closest row that works.
    # just bubble sort! to simulate. prove that this is optimal.
    # want the largest numbers first...
    
#     Hint
# (1/3)
# For each row of the grid calculate the most right 1 in the grid in the array maxRight.

# bubble sort this new array!!!

    # def minSwaps(self, grid: List[List[int]]) -> int:
    #     n = len(grid)
    #     max_right = []

    #     for i in range(n):
    #         for j in range(n-1, -1, -1):
    #             if grid[i][j] == 1:
    #                 max_right.append(j)
    #                 break
    #         else:
    #             max_right.append(-1) # row is all 0's !
        
    #     print(max_right)
    #     # res = 0
    #     # for i in range(n):
    #     #     for j in range(i+1, n):
    #     #         if max_right[i] > max_right[j]:
    #     #             max_right[i], max_right[j] = max_right[j], max_right[i]
    #     #             res += 1
    #     #             # res += j-i
    #     #             print(i,j, max_right)

    #     res = 0
    #     for _ in range(n):
    #         for j in range(n-_-1):
    #             if max_right[j] > max_right[j+1]:
    #                 max_right[j], max_right[j+1] = max_right[j+1], max_right[j]
    #                 res += 1
    #                 # res += j-i
    #                 print(i,j, max_right)
        

    #     print(max_right)
    #     return res if all(max_right[i] <= i for i in range(n)) else -1

    # above will WA on: grid =
# [[1,0,0,0,0,0],[0,1,0,1,0,0],[1,0,0,0,0,0],[1,1,1,0,0,0],[1,1,0,1,0,0],[1,0,0,0,0,0]]
# Use Testcase
# Stdout
# [0, 3, 0, 2, 3, 0]
# 5 1 [0, 0, 3, 2, 3, 0]
# 5 2 [0, 0, 2, 3, 3, 0]
# 5 4 [0, 0, 2, 3, 0, 3]
# 5 3 [0, 0, 2, 0, 3, 3]
# 5 2 [0, 0, 0, 2, 3, 3]
# [0, 0, 0, 2, 3, 3]
# Output
# 5
# Expected
# 2

# the reason above buble sort doesnt work, is we don't necessarily want SORTED ORDER... ex. # Here the "descending" order is not strict. arr is good as long as arr[i] >= n - i - 1. For example, arr = [4,3,4,4] is valid.
# as long as all(max_right[i] <= i for i in range(n)) is TRUE, then we consider 'max_right' to be 'sorted'

    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        max_right = []

        for i in range(n):
            for j in range(n-1, -1, -1):
                if grid[i][j] == 1:
                    max_right.append(j)
                    break
            else:
                max_right.append(-1) # row is all 0's !
        
        print(max_right)
        res = 0
        for i in range(n):
            target = i # we aim for max_right[i] <= i to hold.
            if max_right[i] <= target: continue

            for j in range(i+1, n):
                # ex. [2,1,0]
                # #   identify we need 0 at index 0
                # [2,0,1] (swap index 1 and 2)
                #[0,2,1] # swap it down, (index 0 and 1) the rest is the same
                # hence we have: max_right[i], max_right[i+1:j+1] = max_right[j], max_right[i:j]

                # greedy, look for the FIRST/SMALLEST index j that works/holds...
                if max_right[j] <= target:
                    # tmp = max_right[j]
                    # max_right[i+1:j+1] = max_right[i:j]
                    # max_right[i] = tmp
                    max_right[i], max_right[i+1:j+1] = max_right[j], max_right[i:j]
                    res += j-i # NOT += 1
                    # print(i,j, max_right)
                    break
            else:
                return -1
        
        print(max_right)
        return res
        #return res if all(max_right[i] <= i for i in range(n)) else -1
            

# Explaination

# First we count the number of trailing zeroes in each row and store the numbers in arr.

# For grid = [[0,0,1],[1,1,0],[1,0,0]], we have arr = [0,1,2].

# We are hoping to rearrange arr so that arr[i] >= n - i - 1. In this case, arr will become [2,1,0] after rearrangement.

# We can use greedy approach to do the rearrangement:

# find the smallest j such that j >= i and arr[j] >= n - i - 1
# do j - i swaps to bring arr[j] to index i
# The reason why greedy approach works is that arr will be in "descending" order after rearragement, so it's fine to push smaller numbers downwards.

# Here the "descending" order is not strict. arr is good as long as arr[i] >= n - i - 1. For example, arr = [4,3,4,4] is valid.


# Complexity

# Time complexity: O(N^2)
# Space complexity: O(N)


# Python

# class Solution:
#     def minSwaps(self, grid: List[List[int]]) -> int:
#         n = len(grid)
        
#         def count(arr):
#             ans = 0
#             for i in range(n-1, -1, -1):
#                 if arr[i] == 0:
#                     ans += 1
#                 else:
#                     break
#             return ans
            
#         arr = [count(row) for row in grid]
#         ans = 0
#         for i in range(n):
#             target = n - i - 1
#             if arr[i] >= target:
#                 continue
#             flag = False
#             for j in range(i+1, n):
#                 if arr[j] >= target:
#                     flag = True
#                     ans += (j - i)
#                     arr[i+1:j+1] = arr[i:j]
#                     break
#             if not flag:
#                 return -1
        
#         return ans

    # concise. 
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        max_right = []

        for i in range(n):
            for j in range(n-1, -1, -1):
                if grid[i][j] == 1:
                    max_right.append(j)
                    break
            else:
                max_right.append(-1) # row is all 0's !
        
        res = 0
        for i in range(n):
            for j in range(i, n):
                if max_right[j] <= i:
                    max_right[i], max_right[i+1:j+1] = max_right[j], max_right[i:j]
                    res += j-i
                    break
            else:
                return -1
        
        return res
        


17700