Minimum swaps to arrange a binary grid

Array Greedy Matrix

49.3% acceptance

Feb 25, 2026

585

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_swaps(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    // Compute trailing zeros for each row
    let mut zeros: Vec<usize> = grid.iter().map(|row| {
      let mut z = 0;
      for j in (0..n).rev() {
        if row[j] == 0 { z += 1; } else { break; }
      }
      z
    }).collect();

    let mut swaps = 0;
    for i in 0..n {
      let needed = n - 1 - i;
      // Find the first row at or below i with >= needed trailing zeros
      let mut found = None;
      for j in i..n {
        if zeros[j] >= needed {
          found = Some(j);
          break;
        }
      }
      match found {
        None => return -1,
        Some(j) => {
          // Bubble row j up to position i
          for r in (i+1..=j).rev() {
            zeros.swap(r, r-1);
            swaps += 1;
          }
        }
      }
    }
    swaps as i32
  }
}