Minimum Swaps to Arrange a Binary Grid solution and explanation
9 more videos on this problem
Minimum Swaps to Arrange a Binary Grid | Intuition | Dry Run | Leetcode 1536 | codestorywithMIKcodestorywithMIK · 23:02 · 11K views
1536. Minimum Swaps to Arrange a Binary Grid | Leetcode Daily - PythonLeetcode Daily · 7:14 · 1K views
LeetCode 1536. Minimum Swaps to Arrange a Binary GridHappy Coding · 14:18 · 1K views
Minimum Swaps to Arrange Binary Grid | LeetCode 1536 | Greedy Selection & Trailing ZerosSanyam IIT Guwahati · 16:52 · 1K views
Minimum Swaps to Arrange a Binary Grid | Leetcode 1536Competitive Coding · 8:08 · 1K views
1536. Minimum Swaps to Arrange a Binary Grid (Leetcode Medium)Programming Live with Larry · 11:08 · 929 views
Daily Leetcode #2162: Mar 02, 2026 - 1536. Minimum Swaps to Arrange a Binary GridProgramming Live with Larry · 16:20 · 779 views
LeetCode 1536. Minimum Swaps to Arrange a Binary Grid (Python)AH Tech · 7:54 · 747 views
Minimum Swaps to Arrange a Binary Grid | LeetCode 1536 | Greedy | Java Code | Developer CoderDeveloper Coder · 19:33 · 376 views
Minimum Swaps to Arrange a Binary Grid | Leetcode 1536 | Java - Hindi | Daily LeetcodeKernel Queen 👑 · 8:55 · 294 views
The problem
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.
A grid is said to be valid if all the cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.
The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).
Example 1:
Input: grid = [[0,0,1],[1,1,0],[1,0,0]] Output: 3
Example 2:
Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] Output: -1 Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,1]] Output: 0
Constraints:
n == grid.length== grid[i].length1 <= n <= 200grid[i][j]is either0or1
Approach overview
Problem Overview: You are given an n x n binary grid. The goal is to reorder rows using adjacent swaps so that for every row i, the number of trailing zeros is at least n - i - 1. If no ordering satisfies this constraint, return -1. The challenge is minimizing the number of adjacent row swaps required.
Approach 1: Greedy Method to Track Trailing Zeros (O(n2) time, O(n) space)
Start by computing the number of trailing zeros for each row. Store these values in an array. For row i, you need at least n - i - 1 trailing zeros to place that row at position i. Scan downward from i to find the first row that satisfies the requirement. Once found, move that row upward using adjacent swaps, which costs the distance moved. This greedy strategy works because placing the earliest valid row preserves flexibility for later rows. The algorithm mainly uses array traversal and counting, making it a classic combination of array manipulation and greedy decision making. Time complexity is O(n^2) due to repeated scans and swaps, while space complexity is O(n) for storing trailing zero counts.
Approach 2: Advanced Counting from Bottom to Top (O(n2) time, O(n) space)
This variation processes the grid from the bottom toward the top while maintaining counts of rows that already satisfy each trailing-zero requirement. First compute trailing zeros for every row in the matrix. Then iterate over required positions and look for rows that meet the constraint. Instead of repeatedly scanning the full list, you conceptually treat rows as a movable sequence and count how far a valid row must travel upward. The number of swaps equals the difference between the row’s current index and its target index. This method emphasizes counting and positional adjustments rather than explicitly simulating every swap, though the complexity remains O(n^2). It provides a cleaner mental model for understanding why the greedy choice is optimal.
Recommended for interviews: The greedy trailing-zero approach is the expected solution. Interviewers want to see you recognize that each row has a minimum trailing-zero requirement and that selecting the nearest valid row minimizes swaps. Starting with the trailing-zero calculation shows strong problem decomposition, while the greedy placement demonstrates algorithmic intuition. Even though the complexity is O(n^2), it comfortably fits the problem constraints and is considered the optimal practical solution.
Approach 1: Approach 1: Greedy Method to Track Trailing Zeros
This greedy method counts the number of trailing zeros in each row and then tries to move rows upwards to match each row's position with the trailing zero requirement.
The idea is to calculate the minimum number of zeroes required on the right side for each row and then check if a row can be moved up by swapping to meet the requirement.
class Solution:
def minSwaps(self, grid: List[List[int]]) -> int:
n = len(grid)
trailing_zeros = [0] * n
for i in range(n):
count = 0
for j in range(n - 1, -1, -1):
if grid[i][j] == 0:
count += 1
else:
break
trailing_zeros[i] = count
swaps = 0
for i in range(n):
required = n - 1 - i
j = i
while j < n and trailing_zeros[j] < required:
j += 1
if j == n:
return -1
while j > i:
trailing_zeros[j], trailing_zeros[j - 1] = trailing_zeros[j - 1], trailing_zeros[j]
j -= 1
swaps += 1
return swapsclass Solution {
public int minSwaps(int[][] grid) {
int n = grid.length;
int[] trailingZeros = new int[n];
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 0) count++;
else break;
}
trailingZeros[i] = count;
}
int swaps = 0;
for (int i = 0; i < n; i++) {
int required = n - 1 - i;
int j = i;
while (j < n && trailingZeros[j] < required) j++;
if (j == n) return -1;
while (j > i) {
int temp = trailingZeros[j];
trailingZeros[j] = trailingZeros[j - 1];
trailingZeros[j - 1] = temp;
j--;
swaps++;
}
}
return swaps;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minSwaps(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> trailingZeros(n);
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 0) count++;
else break;
}
trailingZeros[i] = count;
}
int result = 0;
for (int i = 0; i < n; i++) {
int required = n - 1 - i;
int j = i;
while (j < n && trailingZeros[j] < required) j++;
if (j == n) return -1;
while (j > i) {
swap(trailingZeros[j], trailingZeros[j - 1]);
j--;
result++;
}
}
return result;
}var minSwaps = function(grid) {
const n = grid.length;
const trailingZeros = Array(n).fill(0);
for (let i = 0; i < n; i++) {
let count = 0;
for (let j = n - 1; j >= 0; j--) {
if (grid[i][j] === 0) count++;
else break;
}
trailingZeros[i] = count;
}
let swaps = 0;
for (let i = 0; i < n; i++) {
const required = n - 1 - i;
let j = i;
while (j < n && trailingZeros[j] < required) j++;
if (j === n) return -1;
while (j > i) {
[trailingZeros[j], trailingZeros[j - 1]] = [trailingZeros[j - 1], trailingZeros[j]];
j--;
swaps++;
}
}
return swaps;
};#include <stdio.h>
#define min(a, b) (((a) < (b)) ? (a) : (b))
int minSwaps(int grid[200][200], int gridSize, int *gridColSize) {
int trailingZeros[gridSize];
for (int i = 0; i < gridSize; i++) {
int count = 0;
for (int j = gridSize - 1; j >= 0; j--) {
if (grid[i][j] == 0) count++;
else break;
}
trailingZeros[i] = count;
}
int swaps = 0;
for (int i = 0; i < gridSize; i++) {
int target = gridSize - 1 - i;
int j = i;
while (j < gridSize && trailingZeros[j] < target) {
j++;
}
if (j == gridSize) return -1;
while (j > i) {
int temp = trailingZeros[j];
trailingZeros[j] = trailingZeros[j - 1];
trailingZeros[j - 1] = temp;
j--;
swaps++;
}
}
return swaps;
}using System;
public class Solution {
public int MinSwaps(int[][] grid) {
int n = grid.Length;
int[] trailingZeros = new int[n];
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 0) count++;
else break;
}
trailingZeros[i] = count;
}
int swaps = 0;
for (int i = 0; i < n; i++) {
int required = n - 1 - i;
int j = i;
while (j < n && trailingZeros[j] < required) j++;
if (j == n) return -1;
while (j > i) {
int temp = trailingZeros[j];
trailingZeros[j] = trailingZeros[j - 1];
trailingZeros[j - 1] = temp;
j--;
swaps++;
}
}
return swaps;
}
}This Python implementation follows a similar logic, computing trailing zeros and attempting to match rows to required positions. It utilizes Python’s list and iteration functionalities extensively.
Time Complexity: O(n^2), two loops over the grid ensure trailing zeros meet required constraints. Space Complexity: O(n) to store trailing zero counts.
Approach 2: Approach 2: Advanced Counting from Bottom to Top
This method involves counting the minimum number of swaps directly by halting if a grid row, while positioned at top positions, meets the required trailing zero count. Start from the bottom row and work upwards, swapping minimally to achieve target zero counts.
class Solution:
def minSwaps(self, grid: List[List[int]]) -> int:
n = len(grid)
zeros = []
for row in grid:
count = 0
for val in reversed(row):
if val == 0:
count += 1
else:
break
zeros.append(count)
swaps = 0
for i in range(n):
required = n - i - 1
j = i
while j < n and zeros[j] < required:
j += 1
if j == n:
return -1
swaps += j - i
while j > i:
zeros[j], zeros[j-1] = zeros[j-1], zeros[j]
j -= 1
return swapsimport java.util.ArrayList;
class Solution {
public int minSwaps(int[][] grid) {
ArrayList<Integer> zeros = new ArrayList<>();
int n = grid.length, swaps = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 0) count++;
else break;
}
zeros.add(count);
}
for (int i = 0; i < n - 1; i++) {
int required = n - i - 1, j = i;
while (j < n && zeros.get(j) < required) j++;
if (j == n) return -1;
swaps += j - i;
while (j > i) {
zeros.set(j, zeros.set(j - 1, zeros.get(j)));
j--;
}
}
return swaps;
}
}#include <vector>
#include <iterator>
using namespace std;
int minSwaps(vector<vector<int>>& grid) {
vector<int> zeros;
int n = grid.size(), swaps = 0;
for (auto &row : grid) {
auto it = find(row.rbegin(), row.rend(), 1);
zeros.push_back(distance(row.rbegin(), it));
}
for (int i = 0; i < n - 1; ++i) {
int required = n - i - 1, j = i;
while (j < n && zeros[j] < required) ++j;
if (j == n) return -1;
swaps += j - i;
while (j > i) swap(zeros[j], zeros[j - 1]), --j;
}
return swaps;
}var minSwaps = function(grid) {
const n = grid.length
const zeros = new Array(n).fill(0);
grid.forEach((row, i) => {
let count = 0;
for (let j = n - 1; j >= 0; j--) {
if (row[j] === 0) count++;
else break;
}
zeros[i] = count;
});
let swaps = 0;
for (let i = 0; i < n; i++) {
const required = n - i - 1;
let j = i;
while (j < n && zeros[j] < required) j++;
if (j === n) return -1;
swaps += j - i;
while (j > i) {
[zeros[j], zeros[j - 1]] = [zeros[j - 1], zeros[j]];
j--;
}
}
return swaps;
};#include <stdio.h>
#include <stdbool.h>
int calculateTrailingZeros(int row[], int size) {
int count = 0;
for (int i = size - 1; i >= 0; i--) {
if (row[i] == 0) count++;
else break;
}
return count;
}
int minSwaps(int grid[200][200], int gridSize) {
int zeros[gridSize], swaps = 0;
for (int i = 0; i < gridSize; i++) {
zeros[i] = calculateTrailingZeros(grid[i], gridSize);
}
int valid = 1;
for (int i = 0; i < gridSize - 1; i++) {
int required = gridSize - i - 1;
int j = i;
while (j < gridSize && zeros[j] < required) j++;
if (j == gridSize) return -1;
swaps += j - i;
for (int k = j; k > i; k--) {
int temp = zeros[k];
zeros[k] = zeros[k - 1];
zeros[k - 1] = temp;
}
}
return swaps;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinSwaps(int[][] grid) {
int swaps = 0, n = grid.Length;
var zeros = new List<int>();
foreach (var row in grid) {
int count = 0;
for (int j = n - 1; j >= 0; j--) {
if (row[j] == 0) count++;
else break;
}
zeros.Add(count);
}
for (int i = 0; i < n; i++) {
int required = n - i - 1, j = i;
while (j < n && zeros[j] < required) j++;
if (j == n) return -1;
swaps += j - i;
while (j > i) {
zeros[j] = zeros[j - 1];
j--;
}
}
return swaps;
}
}Python approach applies an inner counting and top-to-bottom strategic zeros swap, balancing sparse grid distributions with minimal shifts upwards.
Time Complexity: O(n^2), given interplaying indices for local restoration. Space Complexity: O(n).
Approach 3: Greedy
We process row by row. For the i-th row, the position of the last '1' must be less than or equal to i. We find the first row that meets the condition in [i, n), denoted as k. Then, starting from the k-th row, we swap the adjacent two rows upwards until the i-th row.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the side length of the grid.
function minSwaps(grid: number[][]): number {
const n = grid.length;
const pos: number[] = Array(n).fill(-1);
for (let i = 0; i < n; ++i) {
for (let j = n - 1; ~j; --j) {
if (grid[i][j] === 1) {
pos[i] = j;
break;
}
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
let k = -1;
for (let j = i; j < n; ++j) {
if (pos[j] <= i) {
ans += j - i;
k = j;
break;
}
}
if (k === -1) {
return -1;
}
for (; k > i; --k) {
[pos[k], pos[k - 1]] = [pos[k - 1], pos[k]];
}
}
return ans;
}func minSwaps(grid [][]int) (ans int) {
n := len(grid)
pos := make([]int, n)
for i := range pos {
pos[i] = -1
}
for i := 0; i < n; i++ {
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 1 {
pos[i] = j
break
}
}
}
for i := 0; i < n; i++ {
k := -1
for j := i; j < n; j++ {
if pos[j] <= i {
ans += j - i
k = j
break
}
}
if k == -1 {
return -1
}
for ; k > i; k-- {
pos[k], pos[k-1] = pos[k-1], pos[k]
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Method to Track Trailing Zeros | Time Complexity: O(n^2), two loops over the grid ensure trailing zeros meet required constraints. Space Complexity: O(n) to store trailing zero counts. |
| Approach 2: Advanced Counting from Bottom to Top | Time Complexity: O(n^2), given interplaying indices for local restoration. Space Complexity: O(n). |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Tracking of Trailing Zeros | O(n^2) | O(n) | General case. Most intuitive solution and commonly expected in coding interviews. |
| Bottom-to-Top Counting Strategy | O(n^2) | O(n) | Useful when reasoning about row positions and swap distances instead of explicitly simulating swaps. |
Frequently asked questions
Is Minimum Swaps to Arrange a Binary Grid easy or hard?
The problem is rated Medium on LeetCode. The main difficulty lies in recognizing that trailing zeros determine valid row placement and that a greedy swap strategy minimizes operations. Once that insight is clear, the implementation is straightforward.
Minimum Swaps to Arrange a Binary Grid Python/Java solution
Most implementations compute trailing zeros for every row, store them in a list or array, then iterate over required positions while searching for the nearest valid row. The same greedy logic works in Python, Java, C++, and other languages with O(n^2) time complexity.
How to solve Minimum Swaps to Arrange a Binary Grid in O(n)?
An O(n) solution is not achievable because each row may need to be compared with multiple rows to find a valid candidate. The accepted optimal approach is O(n^2), where you compute trailing zeros and greedily bring the nearest valid row to the correct position using adjacent swaps.
What is the best approach for Minimum Swaps to Arrange a Binary Grid?
The most effective approach is a greedy strategy based on counting trailing zeros in each row. For position i, you find the nearest row below it with at least n-i-1 trailing zeros and move it upward using adjacent swaps. This guarantees the minimum swaps because choosing the closest valid row minimizes movement cost. The overall time complexity is O(n^2) with O(n) extra space.
Is Minimum Swaps to Arrange a Binary Grid asked at Google/Amazon/Meta?
Problems involving greedy row reordering and matrix constraints frequently appear in interviews at companies like Amazon and Google. Variants testing greedy reasoning, swap minimization, and matrix traversal are common in mid-level algorithm rounds.
What data structure is used in Minimum Swaps to Arrange a Binary Grid?
The core data structure is an array storing the number of trailing zeros for each row. The algorithm then performs sequential scans and simulated swaps on this array. The grid itself is treated as a matrix while counting trailing zeros.
What is the time complexity of Minimum Swaps to Arrange a Binary Grid?
The optimal solution runs in O(n^2) time. You first compute trailing zeros for all rows in O(n^2) total work, then repeatedly scan rows to find one that satisfies the trailing-zero requirement for each position. Space complexity is O(n) for storing the trailing zero counts.