Minimum Swaps to Arrange a Binary Grid — Problem & Solution
Minimum Swaps to Arrange a Binary Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Swaps to Arrange a Binary Grid is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Matrix
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
grid is an n x n binary matrix. In one step you may swap two adjacent rows.
The grid is valid when every cell strictly above the main diagonal is 0 — that is, grid[i][j] == 0 whenever j > i.
Return the minimum number of steps needed to make the grid valid, or -1 if no sequence of swaps can do it.
Example 1
Input: grid = [[1,1,0],[1,0,0],[0,1,1]]
Output: 1
Explanation: Swapping the first two rows gives `[[1,0,0],[1,1,0],[0,1,1]]`.
Example 2
Input: grid = [[0,0,1],[0,1,0],[1,0,0]]
Output: 3
Explanation: The last row must climb to the top (two swaps), then the old first row must move below the old second row (one more).
Example 3
Input: grid = [[0,1,0],[1,0,1],[0,0,1]]
Output: -1
Explanation: The top row needs two trailing zeros and no row has them.
Constraints
n == grid.length == grid[i].length1 <= n <= 200grid[i][j] is 0 or 1
Hints for Minimum Swaps to Arrange a Binary Grid
Hint 1
Only one number per row matters: how many zeros it ends with.
Hint 2
Row
i(0-indexed) of a valid grid must end with at leastn - 1 - izeros, so the top row has the strictest requirement.Hint 3
Fill positions from the top: bring up the nearest row below that meets the requirement, paying one swap per row it passes. If no such row exists, return
-1.
How to solve Minimum Swaps to Arrange a Binary Grid
Reduce each row to its count of trailing zeros, then fill the positions top-down, each time bubbling up the closest row that is good enough.
Approach
- Compute
tz[r], the number of trailing zeros of rowr. - For
i = 0 .. n-1, find the firstj >= iwithtz[j] >= n - 1 - i. If none, return-1. - Move it to position
iby adjacent swaps (j - iof them), shifting the rows in between down by one, and addj - ito the answer. - Return the total.
Why it works
Requirements only get weaker going down. Any row that satisfies position i also satisfies every later position, so taking the nearest qualifying row is never worse: rows passed over keep their relative order and only move down, where their requirement is weaker, and moving a farther row instead would cost at least as many swaps. A standard exchange argument turns any optimal sequence into the greedy one without increasing its length.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Choose the nearest qualifying row, not the one with the most trailing zeros — that would waste a strong row on an easy position and can cost extra swaps.
- Rows move by adjacent swaps, so moving row
jtoicostsj - iand shifts the others; simulate the shift. - Count trailing zeros, not total zeros.
Reference solution
Python
from typing import List
def minSwaps(grid: List[List[int]]) -> int:
n = len(grid)
tz = []
for row in grid:
z = 0
j = n - 1
while j >= 0 and row[j] == 0:
z += 1
j -= 1
tz.append(z)
swaps = 0
for i in range(n):
j = i
while j < n and tz[j] < n - 1 - i:
j += 1
if j == n:
return -1
swaps += j - i
tz.insert(i, tz.pop(j))
return swapsJava
public static int minSwaps(int[][] grid) {
int n = grid.length;
int[] tz = new int[n];
for (int r = 0; r < n; r++) {
int z = 0;
for (int c = n - 1; c >= 0 && grid[r][c] == 0; c--) z++;
tz[r] = z;
}
int swaps = 0;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && tz[j] < n - 1 - i) j++;
if (j == n) return -1;
for (; j > i; j--) {
int t = tz[j]; tz[j] = tz[j - 1]; tz[j - 1] = t;
swaps++;
}
}
return swaps;
}C++
int minSwaps(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> tz(n, 0);
for (int r = 0; r < n; r++) {
int z = 0;
for (int c = n - 1; c >= 0 && grid[r][c] == 0; c--) z++;
tz[r] = z;
}
int swaps = 0;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && tz[j] < n - 1 - i) j++;
if (j == n) return -1;
for (; j > i; j--) {
swap(tz[j], tz[j - 1]);
swaps++;
}
}
return swaps;
}JavaScript
var minSwaps = function(grid) {
var n = grid.length, tz = [];
for (var r = 0; r < n; r++) {
var z = 0;
for (var c = n - 1; c >= 0 && grid[r][c] === 0; c--) z++;
tz.push(z);
}
var swaps = 0;
for (var i = 0; i < n; i++) {
var j = i;
while (j < n && tz[j] < n - 1 - i) j++;
if (j === n) return -1;
for (; j > i; j--) {
var t = tz[j]; tz[j] = tz[j - 1]; tz[j - 1] = t;
swaps++;
}
}
return swaps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms