Problem Statement in English

You’re given an n x n binary grid. You can swap two adjacent rows of the grid any number of times.

Your task is to arrange the grid such that all the cells above the main diagonal are 0. Return the minimum number of swaps needed to achieve this configuration, or -1 if it’s not possible.

Approach

There are 2 steps to this problem:

  • First, we need to count the number of trailing zeros in each row and store it in a list.
  • Then, we need to iterate through the list and for each index, we need to find the first row below it that has enough trailing zeros and swap it up using adjacent swaps.

You see, we don’t need it to be a perfectly triangular upper matrix of zeros, we just need to ensure that for each row i, there are at least n - 1 - i trailing zeros.

So, we can iterate through the list of trailing zeros and for each index i, we need to find the first row below it that has at least n - 1 - i trailing zeros. If we find such a row, we can swap it up using adjacent swaps and increment our result by the number of swaps needed.

And we’re done!

Solution in Python


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

        # Store trailing zero counts in a list (instead of hashmap)
        trailing = []

        for i in range(M):
            count = 0
            for j in reversed(range(N)):
                if grid[i][j] == 0:
                    count += 1
                else:
                    break
            trailing.append(count)

        res = 0

        for index in range(N):
            required = N - 1 - index
            loc = index

            # Find first row below with enough trailing zeros
            while loc < N and trailing[loc] < required:
                loc += 1

            if loc == N:
                return -1

            # Bubble up using adjacent swaps
            while loc > index:
                trailing[loc], trailing[loc - 1] = trailing[loc - 1], trailing[loc]
                res += 1
                loc -= 1

        return res

Complexity

  • Time: $O(N^2)$
    Since we’re doing a nested loop to find the first row with enough trailing zeros and then bubble it up.

  • Space: $O(N)$
    Since we store the trailing zero counts in a list.

Mistakes I Made

I messed up the bubbling mechanism and had to look it up :(

And we are done.