Skip to main content
Talentd

Minimum Swaps to Arrange a Binary Grid - Solution & Explanation

MediumArrayGreedyMatrix15 min readAsked at: Amazon, Bloomberg
Practice this problem

Problem Statement

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].length
  • 1 <= n <= 200
  • grid[i][j] is either 0 or 1

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.

The function minSwaps is implemented to calculate the number of trailing zeros for each row and tries to position them correctly by swapping rows up when necessary. The inner loop finds the closest row with enough trailing zeros to swap in place.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), as we iterate over the grid twice to find trailing zeros and perform necessary swaps. Space Complexity: O(n) for storing trailing zero counts.

Try this approach in the editor →

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.

The C approach decomposes row trailing zeros and aligns these with minimum bottom-to-top swapping, moving upwards and maintaining swap count or returning -1 for an impossible task.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), iterating primarily for least swaps, incrementally. Space Complexity: O(n) to store zero counts.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Method to Track Trailing Zeros

Time Complexity: O(n^2), as we iterate over the grid twice to find trailing zeros and perform necessary swaps. Space Complexity: O(n) for storing trailing zero counts.

Approach 2: Advanced Counting from Bottom to Top

Time Complexity: O(n^2), iterating primarily for least swaps, incrementally. Space Complexity: O(n) to store zero counts.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Tracking of Trailing ZerosO(n^2)O(n)General case. Most intuitive solution and commonly expected in coding interviews.
Bottom-to-Top Counting StrategyO(n^2)O(n)Useful when reasoning about row positions and swap distances instead of explicitly simulating swaps.

Video Solution

Minimum Swaps to Arrange a Binary Grid | Intuition | Dry Run | Leetcode 1536 | codestorywithMIK • codestorywithMIK • 11,360 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Swaps to Arrange a Binary Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays