Problem statement

https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid/

Solution

First, we need to find for each row the most right 1: it will be the smallest position where we can but this row. Now we have bunch of numbers and we want to swap them, such that A[i] <= i. We check that we can do it (using sort) and then use simulation, swapping pairs in greedy way. Notice that this part can be done with binary indexed trees in O(n log n), but it will not help a lot, because we still need O(n^2) to do the first part.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def minSwaps(self, G):
        n = len(G)
        A = [-1] * n
        for j, row in enumerate(G):
            for i in range(n):
                if row[i] == 1: A[j] = i
        
        if any(x > i for i, x in enumerate(sorted(A))):
            return -1
        
        ans = 0
        for i in range(n):
            for j in range(i, n):
                if A[j] <= i:
                    idx = j
                    break
                    
            for j in range(idx, i, -1):
                A[j], A[j-1] = A[j-1], A[j]
                ans += 1
                
        return ans