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.

Description Hints 3 Solution Video 23:02

1536. Minimum Swaps to Arrange a Binary Grid

Medium70.1% acceptance2 companies

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

Asked at 2 companies

Bloomberg Amazon

Topics

Hints open one at a time

Hint 1

For each row of the grid calculate the most right 1 in the grid in the array maxRight.

Hint 2

To check if there exist answer, sort maxRight and check if maxRight[i] ≤ i for all possible i's.

Hint 3

If there exist an answer, simulate the swaps.

23:02

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minSwaps(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[0,0,1],[1,1,0],[1,0,0]]

Input

[[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]

Input

[[1,0,0],[1,1,0],[1,1,1]]

Your code is saved on this device.Solution