Problem Explanation

Given a square grid with rows and columns of equal n length, we need to make all cells above the main diagonal to 0, or find out if it's not possible. We only have one operation that we can perform: swap two adjacent rows.

A valid grid is where all cells above the main diagonal are 0. The main diagonal of a square grid starts from (1,1) up to (n,n). We should return the minimum number of adjacent swaps to make the grid valid, or if it's impossible, return -1.

For instance, given a grid [[0,0,1],[1,1,0],[1,0,0]], we can make three swaps: Swap row 2 and 3, row 2 and 1, and then again row 2 and 3, such that all cells above the main diagonal become 0. So, the output for this case is 3.

Approach

To make the grid valid, each row i in the grid must have at least (n-i) zeros as appendages at the end of the row. We can count the number of trailing zeros for each row and store it in suffixZeros. Then, for each row i from the top to bottom, we find the first row j that has no less trailing zeros than (n-i), and move row j to position i using the adjacent row swap operation. The total number of operations would be our result.

Illustration

Let's take an example for better understanding:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]

SuffixZeros: [1, 2, 3]

We get neededZeros = n - i - 1 = 2 - 0 - 1 = 1. We found that the first row j = 0 (0-indexed) has 1 trailing zero, so we move it to position i = 0, which takes j - i = 0 - 0 = 0 operations.

In the second round, we get neededZeros = n - i - 1 = 2 - 1 - 1 = 0. We found that the second row j = 1 has 2 trailing zeros, which is not less than 0, so we move it to position i = 1, which takes j - i = 1 - 1 = 0 operations.

Adding up all the operations, we got the final result 0 + 0 = 0.

C++ Solution

1
2cpp
3class Solution {
4public:
5  int minSwaps(vector<vector<int>>& grid) {
6    const int n = grid.size();
7    int ans = 0;
8    vector<int> suffixZeros;
9
10    for (const vector<int>& row : grid) {
11      auto itLastOne = find(rbegin(row), rend(row), 1);
12      int suffixZeroCount = distance(rbegin(row), itLastOne);
13      suffixZeros.push_back(suffixZeroCount);
14    }
15
16    for (int i = 0; i < n; ++i) {
17      int neededZeros = n - i - 1;
18      auto it = find_if(begin(suffixZeros) + i, end(suffixZeros), [&](int count) { return count >= neededZeros; });
19      if (it == end(suffixZeros)) return -1;
20      int j = distance(begin(suffixZeros), it);
21      for (int k = j; k > i; --k) suffixZeros[k] = suffixZeros[k - 1];
22      ans += j - i;
23    }
24
25    return ans;
26  }
27};

Python Solution

Here is a python solution that follows a similar approach to the C++ solution:

1
2python
3class Solution:
4    def minSwaps(self, grid):
5        n = len(grid)
6        suffixZeros = [row[::-1].index(1) if 1 in row else n for row in grid]
7        res = 0
8
9        for i in range(n):
10            if suffixZeros[i] < (n - i - 1):
11                for j in range(i + 1, n):
12                    if suffixZeros[j] >= (n - i - 1):
13                        suffixZeros.insert(i, suffixZeros.pop(j))
14                        res += j - i
15                        break
16                else:
17                    return -1
18        return res

Here, we also check for each row i from the top to bottom, and if the count of trailing zeros in the row is less than n-d-1, find a row j no earlier than i with at least n-i-1 trailing zeros and swap this row with the current row i.

JavaScript Solution

This JavaScript solution also uses a similar logic:

1
2javascript
3var minSwaps = function(grid) {
4    const n = grid.length;
5    const suffixZeros = grid.map(row => {
6        let count = 0;
7        for (let i = n - 1; i >= 0 && row[i] === 0; --i) {
8            ++count;
9        }
10        return count;
11    });
12    let res = 0;
13
14    for (let i = 0; i < n; ++i) {
15        let j = i;
16        while (j < n && !(suffixZeros[j] >= n - i - 1)) {
17            ++j;
18        }
19        if (j === n) return -1;
20        const num = suffixZeros[j];
21        suffixZeros.splice(j, 1);
22        suffixZeros.splice(i, 0, num);
23        res += j - i;
24    }
25
26    return res;
27};

In this solution, we calculate the number of trailing zeros in each row of the grid in advance, and perform the operations by swapping the rows to make the number of trailing zeros in each row meet the requirements.

Java Solution

Similarly, here is a Java solution:

1
2java
3class Solution {
4    public int minSwaps(int[][] grid) {
5        int n = grid.length;
6        Integer[] zeros = new Integer[n];
7        for (int i = 0; i < n; i++) {
8            int cnt = 0;
9            for (int j = n - 1; j >= 0 && grid[i][j] == 0; j--)
10                cnt++;
11            zeros[i] = cnt;
12        }
13        
14        int res = 0;
15        for (int i = 0; i < n; i++) {
16            int cur = i;
17            while (cur < n && zeros[cur] < n - i - 1)
18                cur++;
19                
20            if (cur == n) 
21                return -1;
22
23            int cnt = zeros[cur];
24            for (int j = cur; j > i; j--) 
25                zeros[j] = zeros[j - 1];
26                
27            zeros[i] = cnt;
28            res += cur - i;
29        }
30        
31        return res;
32    }
33}

This solution shares a common approach with the earlier ones. We check for each row with sufficient trailing zeros and then make the appropriate swaps. If we can't make a swap that fulfills the requirement, we return -1.