Find all possible stable binary arrays ii

Dynamic Programming Prefix Sum

27.6% acceptance

Feb 23, 2026

You are given 3 positive integers zero, one, and limit. A binary array arr is called stable if: The number of occurrences of 0 in arr is exactly zero. The number of occurrences of 1 in arr is exactly one. Each subarray of arr with a size greater than limit must contain both 0 and 1. Return the total number of stable binary arrays. Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let (z, o, l) = (zero as usize, one as usize, limit as usize);
    let mut dp0 = vec![vec![0i64; o + 1]; z + 1];
    let mut dp1 = vec![vec![0i64; o + 1]; z + 1];

    for i in 1..=z.min(l) {
      dp0[i][0] = 1;
    }
    for j in 1..=o.min(l) {
      dp1[0][j] = 1;
    }

    for i in 1..=z {
      for j in 1..=o {
        dp0[i][j] = (dp0[i-1][j] + dp1[i-1][j]) % MOD;
        if i > l {
          dp0[i][j] = (dp0[i][j] - dp1[i-l-1][j] + MOD) % MOD;
        }
        dp1[i][j] = (dp0[i][j-1] + dp1[i][j-1]) % MOD;
        if j > l {
          dp1[i][j] = (dp1[i][j] - dp0[i][j-l-1] + MOD) % MOD;
        }
      }
    }

    ((dp0[z][o] + dp1[z][o]) % MOD) as i32
  }
}