Problem Description

You are given an n x n binary grid (containing only 0s and 1s). In one step, you can choose two adjacent rows and swap them.

A grid is considered valid when all cells above the main diagonal contain zeros. The main diagonal runs from the top-left corner (1, 1) to the bottom-right corner (n, n).

Your task is to find the minimum number of steps (row swaps) needed to make the grid valid. If it's impossible to make the grid valid through row swaps, return -1.

For example, in a 3x3 grid, the cells above the main diagonal are positions (0,1), (0,2), and (1,2). All these positions must contain zeros for the grid to be valid.

The key insight is that for row i to be valid in the final configuration, all cells from position (i, i+1) to (i, n-1) must be zeros. This means each row needs to have its last 1 appearing at or before column i to be placed as the i-th row in a valid grid.

The solution works by:

1. First calculating for each row the position of its rightmost 1
2. For each target row position i, finding the nearest row below that has its last 1 at position ≤ i
3. Bubbling that row up to position i through adjacent swaps
4. Counting the total number of swaps needed

If at any point no suitable row can be found for a position, the grid cannot be made valid and -1 is returned.

Intuition

To understand this problem, let's first think about what makes a grid valid. For a grid to be valid, all cells above the main diagonal must be zeros. This means:

• Row 0 needs zeros from column 1 to n-1 (requires n-1 trailing zeros)
• Row 1 needs zeros from column 2 to n-1 (requires n-2 trailing zeros)
• Row 2 needs zeros from column 3 to n-1 (requires n-3 trailing zeros)
• And so on...

The key observation is that we can only swap adjacent rows, not modify the content of any row. So each row has a fixed number of trailing zeros that won't change no matter how we rearrange the rows.

This leads us to think: what if we track the rightmost position of 1 in each row? If a row has its last 1 at position j, then it has at least n-1-j trailing zeros. For this row to be placed at position i in the final valid grid, we need j ≤ i.

Now the problem becomes a matching problem: we need to assign rows to positions such that each row i gets a row whose last 1 is at position ≤ i.

Since we can only swap adjacent rows, we should use a greedy approach: for each position i starting from the top, find the closest row below that satisfies the condition (last 1 at position ≤ i). Why the closest? Because moving a row from position j to position i requires exactly j - i swaps, so choosing the closest minimizes the number of swaps for this step.

If at any position i we can't find a suitable row in positions [i, n), then it's impossible to make the grid valid, and we return -1.

This greedy strategy works because once we place a suitable row at position i, we never need to move it again - it will remain valid for all subsequent operations.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy approach where we process each row position from top to bottom.

Step 1: Calculate the rightmost 1 position for each row

First, we create an array pos where pos[i] stores the column index of the rightmost 1 in row i. If a row contains no 1s, we store -1.

pos = [-1] * n
for i in range(n):
    for j in range(n - 1, -1, -1):
        if grid[i][j] == 1:
            pos[i] = j
            break

We iterate from right to left in each row to find the last occurrence of 1.

Step 2: Greedily assign rows to positions

For each target position i (from 0 to n-1), we need to find a row that can be placed there. A row can be placed at position i if its rightmost 1 is at column ≤ i.

for i in range(n):
    k = -1
    for j in range(i, n):
        if pos[j] <= i:
            ans += j - i
            k = j
            break
    if k == -1:
        return -1

We search from position i downwards to find the first row k that satisfies pos[k] <= i. The number of swaps needed to move row k to position i is exactly k - i.

Step 3: Perform the swaps

Once we find a suitable row at position k, we bubble it up to position i through adjacent swaps:

while k > i:
    pos[k], pos[k - 1] = pos[k - 1], pos[k]
    k -= 1

This simulates swapping row k with row k-1, then row k-1 with row k-2, and so on, until the row reaches position i. We only need to update the pos array since we don't need the actual grid configuration.

Time Complexity: O(n²) - For each of the n positions, we may need to search through O(n) rows and perform O(n) swaps.

Space Complexity: O(n) - We only need the pos array to track the rightmost 1 positions.

The algorithm returns the total number of swaps ans if successful, or -1 if it's impossible to make the grid valid.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider this 3×3 grid:

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

Step 1: Calculate rightmost 1 position for each row

We examine each row from right to left to find the last occurrence of 1:

• Row 0: [0,1,1] → rightmost 1 at column 2
• Row 1: [0,0,1] → rightmost 1 at column 2
• Row 2: [0,0,0] → no 1s, so position is -1

Therefore, pos = [2, 2, -1]

Step 2: Process each target position

For a valid grid, we need:

• Row 0: all cells from (0,1) to (0,2) must be 0 → rightmost 1 must be at column ≤ 0
• Row 1: all cells from (1,2) to (1,2) must be 0 → rightmost 1 must be at column ≤ 1
• Row 2: no restrictions → rightmost 1 can be anywhere

Position i = 0:

• Need a row with rightmost 1 at column ≤ 0
• Check rows starting from position 0:
  • Row 0: pos[0] = 2 (2 > 0, doesn't work)
  • Row 1: pos[1] = 2 (2 > 0, doesn't work)
  • Row 2: pos[2] = -1 (-1 ≤ 0, works!)
• Found row 2 at position k = 2
• Swaps needed: 2 - 0 = 2
• Bubble row 2 up to position 0:
  • Swap rows 2 and 1: pos = [2, -1, 2]
  • Swap rows 1 and 0: pos = [-1, 2, 2]
• Total swaps so far: 2

Position i = 1:

• Need a row with rightmost 1 at column ≤ 1
• Check rows starting from position 1:
  • Row 1 (current): pos[1] = 2 (2 > 1, doesn't work)
  • Row 2: pos[2] = 2 (2 > 1, doesn't work)
• No suitable row found!
• Return -1

The grid cannot be made valid because both remaining rows have their rightmost 1 at column 2, which is too far right to be placed at position 1 (where we need the rightmost 1 to be at column ≤ 1).

Let's try a different example where the transformation is possible:

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

Step 1: Calculate positions

• Row 0: rightmost 1 at column 2 → pos[0] = 2
• Row 1: rightmost 1 at column 1 → pos[1] = 1
• Row 2: rightmost 1 at column 0 → pos[2] = 0

So pos = [2, 1, 0]

Position i = 0:

• Need rightmost 1 at column ≤ 0
• Check: Row 0 (pos=2, no), Row 1 (pos=1, no), Row 2 (pos=0, yes!)
• Move row 2 to position 0: 2 swaps
• After bubbling: pos = [0, 2, 1]
• Total swaps: 2

Position i = 1:

• Need rightmost 1 at column ≤ 1
• Check: Row 1 (current, pos=2, no), Row 2 (pos=1, yes!)
• Move row 2 to position 1: 1 swap
• After bubbling: pos = [0, 1, 2]
• Total swaps: 2 + 1 = 3

Position i = 2:

• Need rightmost 1 at column ≤ 2
• Row 2 (current, pos=2, yes!)
• No swaps needed
• Total swaps: 3

The algorithm successfully returns 3 as the minimum number of swaps needed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of three main parts:

1. First loop: Iterates through each row (n iterations) and for each row, iterates through columns to find the rightmost 1 (up to n iterations per row). This gives O(n²).
2. Second nested loop structure:
   • Outer loop runs n times
   • Inner loop searches for a valid row starting from position i, which in worst case examines O(n) rows
   • The while loop performs bubble-up operations, moving element from position k to position i, which takes O(n) swaps in worst case
   • Overall for this part: O(n) × O(n) = O(n²)

Since both parts are O(n²) and execute sequentially, the total time complexity is O(n²).

Space Complexity: O(n)

The algorithm uses a single auxiliary array pos of size n to store the position of the rightmost 1 in each row. All other variables (i, j, k, ans) use constant space. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing Upper Triangular with Lower Triangular Matrix

A frequent mistake is misunderstanding what "valid grid" means. The problem states cells above the main diagonal should be zeros, which means we want an upper triangular matrix. However, many developers incorrectly interpret this as needing zeros below the diagonal.

Wrong interpretation:

# Incorrectly checking for lower triangular
for i in range(n):
    for j in range(i):  # Wrong: checking positions below diagonal
        if grid[i][j] == 1:
            # This is checking the wrong cells

Correct approach:

# For row i to be valid at position i, all cells from (i, i+1) to (i, n-1) must be 0
# This means the rightmost 1 in row i must be at position <= i

Pitfall 2: Not Understanding the Greedy Strategy's Correctness

Some developers try to optimize by finding the "best" row for each position rather than the first suitable one, thinking this might reduce total swaps. This overcomplication is unnecessary and can lead to incorrect solutions.

Incorrect approach:

# Trying to find the "optimal" row with minimum swaps
best_row = -1
min_swaps = float('inf')
for j in range(i, n):
    if pos[j] <= i and j - i < min_swaps:
        min_swaps = j - i
        best_row = j

Why the greedy approach works: The first suitable row we find is always optimal because:

1. We must fill position i with some valid row
2. Any valid row currently below position i will require swaps to reach position i
3. Using the nearest valid row minimizes swaps for this position
4. Delaying this choice doesn't improve future positions

Pitfall 3: Forgetting to Update the Position Array After Swaps

A critical bug occurs when developers count the swaps but forget to actually simulate them by updating the rightmost_one_positions array.

Bug-prone code:

for i in range(n):
    for j in range(i, n):
        if rightmost_one_positions[j] <= i:
            total_swaps += j - i
            # BUG: Not updating the array after "swapping"
            break
    # The array is now inconsistent with the simulated swaps

Correct implementation:

# Must bubble the row up and update positions
while suitable_row_idx > target_row:
    rightmost_one_positions[suitable_row_idx], rightmost_one_positions[suitable_row_idx - 1] = \
        rightmost_one_positions[suitable_row_idx - 1], rightmost_one_positions[suitable_row_idx]
    suitable_row_idx -= 1

Pitfall 4: Off-by-One Errors in Rightmost One Position

Developers sometimes make errors when calculating what position the rightmost 1 needs to be at for each row.

Common mistake:

# Wrong: thinking row i needs rightmost 1 at position < i
if rightmost_one_positions[candidate_row] < target_row:  # Off by one!

Correct logic:

• Row 0 can have its rightmost 1 at position 0 (needs n-1 trailing zeros)
• Row 1 can have its rightmost 1 at position 1 (needs n-2 trailing zeros)
• Row i can have its rightmost 1 at position i (needs n-i-1 trailing zeros)

The condition should be <= not <.