Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Group people by the day they learned the secret. An entire cohort starts sharing after delay days and stops after forget days. The current sharer count can therefore be updated by adding one newly eligible cohort and subtracting one newly forgetting cohort each day.

Approach

Let dp[i] count new learners on zero-based day i, with one learner on day zero. Maintain the active sharer count: add dp[i - delay] and subtract dp[i - forget], treating unavailable earlier cohorts as zero, then assign that count to dp[i]. Apply the modulus throughout. Sum the cohorts from days n - forget through n - 1, which still remember on the final day. The initialized table supplies zero for the code's early-day placeholder accesses.

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * n
        dp[0] = 1
        count = 0

        for i in range(1, n):
            count = (count + dp[i - delay] - dp[i - forget]) % MOD
            dp[i] = count

        res = 0
        for i in range(n - forget, n):
            res = (res + dp[i]) % MOD

        return res

Complexity analysis

Time: O(n) using the rolling count of current sharers. Auxiliary space: O(n) for the day-indexed DP array.