Minimum number of flips to convert binary matrix to zero matrix

Array Hash Table Bit Manipulation Breadth-First Search Matrix

72.4% acceptance

Feb 25, 2026

1007

103

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge. Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot. A binary matrix is a matrix with all cells equal to 0 or 1 only. A zero matrix is a matrix with all cells equal to 0.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_flips(mat: Vec<Vec<i32>>) -> i32 {
    let m = mat.len();
    let n = mat[0].len();
    // Encode matrix as a bitmask
    let mut start = 0u32;
    for i in 0..m {
      for j in 0..n {
        if mat[i][j] == 1 {
          start |= 1 << (i * n + j);
        }
      }
    }
    if start == 0 { return 0; }

    let _total = m * n;
    // BFS over bitmask states
    let mut visited = std::collections::HashSet::new();
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((start, 0));
    visited.insert(start);

    while let Some((state, steps)) = queue.pop_front() {
      for i in 0..m {
        for j in 0..n {
          let mut next = state;
          // flip (i,j) and neighbors
          let positions = [
            (i as i32, j as i32),
            (i as i32 - 1, j as i32),
            (i as i32 + 1, j as i32),
            (i as i32, j as i32 - 1),
            (i as i32, j as i32 + 1),
          ];
          for (r, c) in positions {
            if r >= 0 && r < m as i32 && c >= 0 && c < n as i32 {
              next ^= 1 << (r as usize * n + c as usize);
            }
          }
          if next == 0 { return steps + 1; }
          if !visited.contains(&next) {
            visited.insert(next);
            queue.push_back((next, steps + 1));
          }
        }
      }
    }
    -1
  }
}