Number of People Aware of a Secret - Solution & Explanation

Problem Overview: One person learns a secret on day 1. After delay days they start sharing it with one new person per day. After forget days they forget the secret and stop sharing. Given n, compute how many people still remember the secret at the end of day n.

Approach 1: Dynamic Programming Simulation (O(n) time, O(n) space)

Track the number of people who learn the secret on each day using a DP array dp[i]. If someone learns the secret on day i, they start sharing on day i + delay and stop after day i + forget - 1. Iterate day by day and maintain how many people are currently eligible to share. Each eligible person contributes exactly one new learner per day, so the number of new learners on day d equals the number of active sharers that day.

Efficient implementations maintain a running count of sharers by adding dp[d - delay] when people become eligible and subtracting dp[d - forget] when they forget. This avoids scanning earlier days repeatedly. The approach directly models the process described in the problem and works well for interview settings where clear state transitions matter. Concepts align with dynamic programming and simulation.

Approach 2: Optimized Constant Space Window (O(n) time, O(1) space)

The sharing behavior forms a sliding window of active sharers. Anyone who learned between d - forget + 1 and d - delay can share on day d. Instead of storing the entire DP array, track the rolling sum of people inside this window. Each day you update the window by adding the group that just became eligible to share and removing the group that just forgot.

The number of new learners equals this active sharer count. Maintain the total modulo 1e9 + 7. This approach reduces memory usage by keeping only a few counters rather than a full array, while preserving the same recurrence. The logic resembles queue-style window management commonly seen in queue or prefix-sum based simulations.

Recommended for interviews: The dynamic programming simulation is usually what interviewers expect. It clearly models the lifecycle of each group of people: learn, start sharing, and forget. Once you understand that lifecycle, optimizing the sharer count with a running window demonstrates stronger algorithmic thinking and reduces unnecessary state.