Find all possible stable binary arrays i

Dynamic Programming Prefix Sum

27.1% acceptance

Feb 23, 2026

135

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);
    // dp[i][j][k]: ways using i zeros, j ones, last digit k
    // Use flat 2D arrays dp0[i][j] and dp1[i][j]
    let mut dp0 = vec![vec![0i64; o + 1]; z + 1];
    let mut dp1 = vec![vec![0i64; o + 1]; z + 1];

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

    // Fill dp
    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;
        }
      }
    }
    // Also fill dp1[i][j] for i=0 (already set in base) but for j>=1, i=0 we need recurrence
    // Actually for i=0:
    // dp1[0][j] = dp0[0][j-1] + dp1[0][j-1] - (j > l ? dp0[0][j-l-1] : 0)
    //           = 0 + dp1[0][j-1] - (j > l ? 0 : 0) = dp1[0][j-1]
    // So dp1[0][j] would accumulate, but base case already set dp1[0][j]=1 for j<=l and 0 for j>l.
    // Let me check: for j in 1..=l: dp1[0][j]=1 from base. ✓
    // For j = l+1: dp1[0][l+1] = dp0[0][l] + dp1[0][l] - dp0[0][0] = 0 + 1 - 0 = 1. But should be 0!
    // Hmm, the recurrence would give wrong values for i=0 and j > l.
    // But the base case overrides this: dp1[0][j] = 1 if j<=l else 0. AND the recurrence loop
    // only runs for i >= 1, so it won't touch dp1[0][*]. ✓

    // Similarly, for j=0: dp0[i][0] = 1 if i<=l else 0. The recurrence only runs for j>=1. ✓

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