Leetcode 1536. Minimum Swaps to Arrange a Binary Grid
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
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.