LeetCode 1536 - Minimum Swaps to Arrange a Binary Grid

The problem gives us an n x n binary matrix called grid. Each cell contains either 0 or 1. We are allowed to perform operations where we swap two adjacent rows. The goal is to transform the matrix into a valid configuration using the minimum number of adjacent row swaps.

leetcodemediumarraygreedymatrix

LeetCode Problem 1536

Difficulty: 🟡 Medium
Topics: Array, Greedy, Matrix

Solution

Problem Understanding

The problem gives us an n x n binary matrix called grid. Each cell contains either 0 or 1. We are allowed to perform operations where we swap two adjacent rows. The goal is to transform the matrix into a valid configuration using the minimum number of adjacent row swaps.

A grid is considered valid if every cell above the main diagonal contains 0.

For an n x n matrix, the main diagonal consists of positions:

  • (0,0)
  • (1,1)
  • (2,2)
  • ...
  • (n-1,n-1)

Every position (i, j) where j > i lies above the main diagonal, and all such positions must become 0.

For example, in a 3 x 3 matrix:

x 0 0
x x 0
x x x

Only the cells above the diagonal matter. The values below or on the diagonal can be either 0 or 1.

The important observation is that row i must end with at least n - 1 - i trailing zeros. This is because all columns to the right of the diagonal position must be zero.

For example:

  • Row 0 needs at least n - 1 trailing zeros
  • Row 1 needs at least n - 2 trailing zeros
  • Row 2 needs at least n - 3 trailing zeros
  • ...
  • Row n - 1 needs at least 0 trailing zeros

The constraints are relatively small:

  • 1 <= n <= 200

This means an O(n^2) or even O(n^3) solution is acceptable. However, an exponential brute force search would be far too slow.

Several edge cases are important:

  • The grid may already be valid, requiring 0 swaps.
  • It may be impossible to rearrange rows into a valid order.
  • Multiple rows may have identical trailing zero counts.
  • A required row may only exist far below the current position, forcing many adjacent swaps.

The problem guarantees that the matrix is square and only contains binary values.

Approaches

Brute Force Approach

A brute force strategy would try every possible sequence of adjacent row swaps until either a valid grid is found or all possibilities are exhausted.

One way to think about this is as a shortest path problem:

  • Each matrix configuration is a state.
  • Swapping adjacent rows generates neighboring states.
  • Breadth-first search could theoretically find the minimum swaps.

This approach is correct because BFS guarantees the shortest number of swaps. However, the number of possible row permutations is n!, which becomes astronomically large even for moderate n.

For n = 200, this approach is completely infeasible.

Optimal Greedy Approach

The key insight is that the exact row contents do not matter. What matters is only how many trailing zeros each row contains.

Suppose we compute:

trailingZeros[i] = number of zeros at the end of row i

Then row i in the final arrangement must satisfy:

trailingZeros[i] >= n - 1 - i

We process rows from top to bottom.

At position i, we search downward for the first row that has enough trailing zeros. Once found, we bubble that row upward using adjacent swaps.

Why is this greedy choice optimal?

Because adjacent swaps cost exactly the distance moved upward. Choosing the nearest valid row minimizes swaps locally, and any valid arrangement must place some qualifying row at this position anyway.

This transforms the problem into a simple greedy simulation.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Explores all row permutations
Optimal Greedy O(n²) O(n) Uses trailing zero counts and greedy swapping

Algorithm Walkthrough

  1. Compute the number of trailing zeros for every row.

For each row, scan from right to left until encountering the first 1. Count how many zeros appear at the end.

Example:

[1,0,0,0] -> 3 trailing zeros
[1,1,0,0] -> 2 trailing zeros
[1,1,1,1] -> 0 trailing zeros
  1. Store these counts in an array called trailingZeros.

Example:

trailingZeros = [2,1,0]
  1. Process each target row position from top to bottom.

For row index i, the required number of trailing zeros is:

required = n - 1 - i
  1. Search downward from row i until finding the first row whose trailing zero count satisfies the requirement.
trailingZeros[j] >= required
  1. If no such row exists, return -1.

This means the grid can never become valid. 6. Otherwise, bubble the row upward.

Move row j upward to position i using adjacent swaps. Each upward movement costs one swap.

During this process, swap neighboring entries in the trailingZeros array as well. 7. Add the number of swaps performed to the answer. 8. Continue until all rows are processed. 9. Return the total swap count.

Why it works

For each row position, we must place some row that satisfies the required trailing zero count. Choosing the nearest valid row minimizes the number of swaps needed for the current position. Since swaps only affect row order and do not change trailing zero counts, fixing earlier rows greedily never harms future possibilities. Therefore, the algorithm always produces the minimum number of adjacent swaps.

Python Solution

from typing import List

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)

        # Compute trailing zero counts
        trailing_zeros = []

        for row in grid:
            count = 0

            for value in reversed(row):
                if value == 0:
                    count += 1
                else:
                    break

            trailing_zeros.append(count)

        swaps = 0

        # Process each row position
        for i in range(n):
            required = n - 1 - i

            # Find first row that satisfies requirement
            j = i

            while j < n and trailing_zeros[j] < required:
                j += 1

            # Impossible to satisfy this row
            if j == n:
                return -1

            # Bubble row upward
            while j > i:
                trailing_zeros[j], trailing_zeros[j - 1] = (
                    trailing_zeros[j - 1],
                    trailing_zeros[j],
                )

                swaps += 1
                j -= 1

        return swaps

The implementation begins by computing the trailing zero count for each row. Since only the suffix zeros matter for satisfying the diagonal condition, the actual matrix contents are no longer needed after this preprocessing step.

The main loop processes each target row position. For position i, the algorithm determines how many trailing zeros are required.

It then searches downward for the first row that satisfies the condition. If no such row exists, the function immediately returns -1.

Once a suitable row is found, the implementation repeatedly swaps neighboring entries in the trailing_zeros array until the row reaches its correct position. Each swap corresponds exactly to one adjacent row swap in the actual matrix.

The total number of swaps is accumulated and returned at the end.

Go Solution

func minSwaps(grid [][]int) int {
	n := len(grid)

	// Compute trailing zero counts
	trailingZeros := make([]int, n)

	for i := 0; i < n; i++ {
		count := 0

		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 0 {
				count++
			} else {
				break
			}
		}

		trailingZeros[i] = count
	}

	swaps := 0

	// Process each row position
	for i := 0; i < n; i++ {
		required := n - 1 - i

		j := i

		// Find first valid row
		for j < n && trailingZeros[j] < required {
			j++
		}

		// Impossible case
		if j == n {
			return -1
		}

		// Bubble row upward
		for j > i {
			trailingZeros[j], trailingZeros[j-1] =
				trailingZeros[j-1], trailingZeros[j]

			swaps++
			j--
		}
	}

	return swaps
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used to store trailing zero counts. Since Go does not support Python-style tuple swapping internally for arrays, the swap operation is written explicitly using multiple assignment.

Integer overflow is not a concern because the maximum number of swaps is bounded by n², and n <= 200.

Worked Examples

Example 1

grid = [
  [0,0,1],
  [1,1,0],
  [1,0,0]
]

Step 1: Compute trailing zeros

Row Trailing Zeros
[0,0,1] 0
[1,1,0] 1
[1,0,0] 2 
trailingZeros = [0,1,2]

Step 2: Process rows

Position i = 0

Required trailing zeros:

n - 1 - 0 = 2

Search for first row with at least 2 trailing zeros:

Index Value Valid?
0 0 No
1 1 No
2 2 Yes

Bring row 2 upward:

[0,1,2]
-> swap(2,1)
[0,2,1]

-> swap(1,0)
[2,0,1]

Swaps so far:

2

Position i = 1

Required trailing zeros:

1

Current array:

[2,0,1]

Search downward:

Index Value Valid?
1 0 No
2 1 Yes

Bubble upward:

[2,0,1]
-> swap(2,1)
[2,1,0]

Swaps so far:

3

Position i = 2

Required:

0

Already satisfied.

Final answer:

3

Example 2

grid = [
  [0,1,1,0],
  [0,1,1,0],
  [0,1,1,0],
  [0,1,1,0]
]

Trailing zeros:

[1,1,1,1]

Position i = 0

Required:

3

No row has at least 3 trailing zeros.

Return:

-1

Example 3

grid = [
  [1,0,0],
  [1,1,0],
  [1,1,1]
]

Trailing zeros:

[2,1,0]

Requirements:

Position Required
0 2
1 1
2 0

All rows already satisfy their positions.

No swaps are needed.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each row search and bubbling operation is bounded by n
Space O(n) Stores trailing zero counts

The preprocessing step scans all cells once, which costs O(n²).

During the greedy phase, each row may move upward across multiple positions. In the worst case, the total amount of movement is bounded by O(n²).

The auxiliary space comes from storing the trailing zero counts.

Test Cases

from typing import List

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)

        trailing_zeros = []

        for row in grid:
            count = 0

            for value in reversed(row):
                if value == 0:
                    count += 1
                else:
                    break

            trailing_zeros.append(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],
                )

                swaps += 1
                j -= 1

        return swaps

solution = Solution()

assert solution.minSwaps([
    [0,0,1],
    [1,1,0],
    [1,0,0]
]) == 3  # Example 1

assert solution.minSwaps([
    [0,1,1,0],
    [0,1,1,0],
    [0,1,1,0],
    [0,1,1,0]
]) == -1  # Example 2 impossible case

assert solution.minSwaps([
    [1,0,0],
    [1,1,0],
    [1,1,1]
]) == 0  # Example 3 already valid

assert solution.minSwaps([
    [0]
]) == 0  # Single cell grid

assert solution.minSwaps([
    [0,0],
    [1,0]
]) == 0  # Already valid 2x2

assert solution.minSwaps([
    [1,0],
    [0,0]
]) == 0  # Both rows satisfy requirements

assert solution.minSwaps([
    [1,1,0],
    [1,0,0],
    [1,1,1]
]) == 1  # One swap needed

assert solution.minSwaps([
    [1,1,1],
    [1,1,0],
    [1,0,0]
]) == 3  # Maximum bubbling behavior

assert solution.minSwaps([
    [1,1],
    [1,1]
]) == -1  # No trailing zeros available

assert solution.minSwaps([
    [0,0,0],
    [0,0,0],
    [0,0,0]
]) == 0  # All zeros grid

Test Summary

Test Why
Example 1 Standard case requiring multiple swaps
Example 2 Impossible configuration
Example 3 Already valid grid
Single cell grid Minimum size boundary
Already valid 2x2 Small valid matrix
Multiple valid rows Ensures greedy selection works
One swap needed Simple bubbling scenario
Maximum bubbling Tests repeated adjacent swaps
No trailing zeros Impossible due to insufficient zeros
All zeros grid Every arrangement is valid

Edge Cases

One important edge case is when the grid is already valid. In this situation, every row already satisfies the trailing zero requirement for its position. A buggy implementation might still perform unnecessary swaps. This solution correctly avoids extra work because each row immediately satisfies the condition during the search phase.

Another critical edge case is when no row can satisfy a required position. For example, if the top row requires three trailing zeros but every row only has one trailing zero, no sequence of swaps can ever make the grid valid. The implementation detects this by searching downward and returning -1 if no valid row is found.

A third important edge case involves rows with identical trailing zero counts. Multiple rows may satisfy the same requirement, and choosing the wrong one could increase swaps unnecessarily. The greedy strategy always selects the nearest valid row, ensuring the minimum number of adjacent swaps.

A final edge case occurs when a valid row exists but is far below the current position. In such cases, many adjacent swaps may be required. The implementation handles this correctly by bubbling the row upward one position at a time while accurately counting swaps.