Check if there is a path with equal number of 0s and 1s

Array Dynamic Programming Matrix

51.9% acceptance

Mar 31, 2026

110

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1). Return true if there is a path from (0, 0) to (m - 1, n - 1) that visits an equal number of 0's and 1's. Otherwise return false.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn is_there_a_path(grid: Vec<Vec<i32>>) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    let path_len = m + n - 1;
    if path_len % 2 == 1 {
      return false;
    }
    let offset = path_len as i32;
    let size = (2 * offset + 1) as usize;
    let val = |r: usize, c: usize| -> i32 {
      if grid[r][c] == 0 { -1 } else { 1 }
    };
    let mut dp = vec![vec![false; size]; n];
    dp[0][(val(0, 0) + offset) as usize] = true;
    for j in 1..n {
      let v = val(0, j);
      for s in 0..size {
        if dp[j - 1][s] {
          let ns = s as i32 + v;
          if ns >= 0 && (ns as usize) < size {
            dp[j][ns as usize] = true;
          }
        }
      }
    }
    for i in 1..m {
      let mut new_dp = vec![vec![false; size]; n];
      for j in 0..n {
        let v = val(i, j);
        for s in 0..size {
          if dp[j][s] {
            let ns = s as i32 + v;
            if ns >= 0 && (ns as usize) < size {
              new_dp[j][ns as usize] = true;
            }
          }
        }
        if j > 0 {
          for s in 0..size {
            if new_dp[j - 1][s] {
              let ns = s as i32 + v;
              if ns >= 0 && (ns as usize) < size {
                new_dp[j][ns as usize] = true;
              }
            }
          }
        }
      }
      dp = new_dp;
    }
    dp[n - 1][offset as usize]
  }
}