Number of people aware of a secret

Dynamic Programming Queue Simulation

60.9% acceptance

Feb 25, 2026

1494

163

On day 1, one person discovers a secret. Each person will share the secret with a new person every day, starting from delay days after discovering. Each person will forget the secret forget days after discovering it. A person cannot share on the same day they forgot it. Given an integer n, return the number of people who know the secret at the end of day n (mod 10^9+7).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn people_aware_of_secret(n: i32, delay: i32, forget: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let (delay, forget) = (delay as usize, forget as usize);
    // dp[day] = number of people who discover the secret on day `day`
    // dp[day] = sum(dp[j] for max(1, day-forget+1) <= j <= day-delay)
    let mut dp = vec![0i64; n + 1];
    dp[1] = 1;
    let mut prefix = vec![0i64; n + 2];
    prefix[1] = 1;

    for day in 2..=n {
      let hi = if day > delay { day - delay } else { 0 };
      let lo = if day + 1 > forget { day + 1 - forget } else { 1 };
      let active = if hi >= lo {
        let s_hi = prefix[hi];
        let s_lo = if lo > 1 { prefix[lo - 1] } else { 0 };
        (s_hi - s_lo + MOD) % MOD
      } else {
        0
      };
      dp[day] = active;
      prefix[day] = (prefix[day - 1] + dp[day]) % MOD;
    }

    // People who still know the secret on day n: discovered on days [n-forget+1, n]
    let lo = if n + 1 > forget { n + 1 - forget } else { 1 };
    ((prefix[n] - if lo > 1 { prefix[lo - 1] } else { 0 } + MOD) % MOD) as i32
  }
}