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 either 0 or 1Problem 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.
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.
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.
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.
Time Complexity: O(n^2), iterating primarily for least swaps, incrementally. Space Complexity: O(n) to store zero counts.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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 | — |
| 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. |
Minimum Swaps to Arrange a Binary Grid | Intuition | Dry Run | Leetcode 1536 | codestorywithMIK • codestorywithMIK • 11,110 views views
Watch 9 more video solutions →Practice Minimum Swaps to Arrange a Binary Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor