This problem requires counting the minimum swaps of adjacent rows to make a binary grid valid, where all cells above the main diagonal are zeros. The key is a greedy approach: for each row, determine the rightmost 1, then move rows down to satisfy the invariant without unnecessary swaps. If a row cannot satisfy the zero-above-diagonal requirement, return -1 immediately.
Problem Statement
You are given an n x n binary grid where each element is 0 or 1. In one step, you can swap any two adjacent rows of the grid. A grid is valid if, for every row i, all elements grid[i][j] are zero when j > i, meaning all cells above the main diagonal are zeros.
Return the minimum number of steps needed to make the grid valid. If it is impossible to achieve a valid grid with adjacent row swaps, return -1. For example, given grid = [[0,0,1],[1,1,0],[1,0,0]], the minimum number of swaps is 3, whereas a grid like [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] cannot be made valid and should return -1.
Examples
Example 1
Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3
Example details omitted.
Example 2
Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
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
Example details omitted.
Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 200
- grid[i][j] is either 0 or 1
Solution Approach
Compute the rightmost 1 for each row
For each row, find the index of the rightmost 1. This transforms the matrix into an array maxRight where maxRight[i] represents the last 1 in row i. This allows greedy identification of which rows must be moved to satisfy the invariant above the main diagonal.
Greedy swapping to enforce validity
Iterate through rows top-down. For row i, find the first row j ≥ i where maxRight[j] ≤ i. Swap adjacent rows downward until row j reaches position i, incrementing the swap counter. This ensures each row satisfies the condition without unnecessary rearrangements.
Early termination if impossible
If no suitable row j exists for position i such that maxRight[j] ≤ i, the grid cannot be made valid. Immediately return -1. This prevents wasted computation and handles the primary failure mode of identical rows or blocked 1s.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n^2) due to scanning each row and performing at most n swaps per row. Space complexity is O(n) to store the maxRight array, representing the last 1 in each row, without modifying the original grid.
What Interviewers Usually Probe
- Looking for a clear greedy strategy tied to maxRight positions.
- Expect correct handling of impossible grids returning -1.
- Assessing whether swaps are minimized without unnecessary movements.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to check if no row can satisfy maxRight ≤ i, causing incorrect results.
- Swapping rows non-adjacently rather than only adjacent rows.
- Miscomputing rightmost 1 leading to wrong row selection and extra swaps.
Follow-up variants
- Compute minimum swaps for a triangular subgrid instead of full matrix.
- Allow swapping any rows, not just adjacent ones, changing the greedy logic.
- Find the maximum number of rows already valid before any swaps are required.
How GhostInterview Helps
- Highlights exactly how to compute maxRight for each row, guiding greedy selection.
- Simulates swaps and tracks counts without manually manipulating the matrix.
- Flags impossible configurations early to prevent wasted calculations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for Minimum Swaps to Arrange a Binary Grid?
The primary strategy is a greedy approach using the rightmost 1 in each row to guide adjacent row swaps efficiently.
How do I determine if the grid can be made valid?
Check if, for each row, there exists a row below with maxRight ≤ current index; if not, return -1 immediately.
Can I swap non-adjacent rows?
No, only adjacent row swaps are allowed; the solution must incrementally move rows downward to the correct position.
What is the time complexity of the greedy solution?
Time complexity is O(n^2) because each row may require scanning and moving up to n rows, and space complexity is O(n) for the maxRight array.
How does the maxRight array help in this problem?
It captures the last 1 in each row, allowing the greedy algorithm to determine which rows can be moved to satisfy the zero-above-diagonal invariant efficiently.
Need direct help with Minimum Swaps to Arrange a Binary Grid instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimum Swaps to Arrange a Binary Grid from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given row and column sums, find any valid matrix of non-negative integers that satisfies them.
Open problem page#1727 Largest Submatrix With RearrangementsRearrange columns of a binary matrix to find the largest submatrix of 1s.
Open problem page#1253 Reconstruct a 2-Row Binary MatrixReconstruct a 2-row binary matrix by distributing column sums while respecting upper and lower row limits using greedy placement.
Open problem page