Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Row i needs at least n - i - 1 trailing zeros to clear every cell above the main diagonal. Once a row is fixed, only the remaining rows matter. Choosing the nearest eligible remaining row costs the fewest adjacent swaps and preserves the relative order of all others.

Approach

Replace each row with its trailing-zero count. Process target rows from top to bottom. If the current count is sufficient, leave it. Otherwise find the first lower row meeting the requirement, add its distance to the swap total, and shift the intervening counts down to simulate bringing it upward. Return -1 if no eligible row remains. Fixed positions are never consulted again, so the code only needs to preserve the unplaced suffix accurately.

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

        def tzeros(row):
            c = 0

            for i in range(n - 1, -1, -1):
                if row[i] != 0:
                    break
                c += 1

            return c

        arr = [tzeros(row) for row in grid]
        res = 0

        for i in range(n):
            target = n - i - 1
            if arr[i] >= target:
                continue
            found = False
            for j in range(i + 1, n):
                if arr[j] >= target:
                    res += j - i
                    for k in range(j, i, -1):
                        arr[k] = arr[k - 1]
                    found = True
                    break
            if not found:
                return -1

        return res

Complexity analysis

For an n × n grid, counting trailing zeros costs O(n²) and the repeated search/shift simulation costs O(n²) in the worst case. Total time is O(n²) and auxiliary space is O(n) for the trailing-zero counts.