BinarySearch 0915 Place Zeros Above the Matrix Diagonal

Problem statement

https://binarysearch.com/problems/Place-Zeros-Above-the-Matrix-Diagonal/

Solution

Equal to Leetcode 1536. Minimum Swaps to Arrange a Binary Grid.

Complexity

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

Code

class Solution:
    def solve(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