Watch 10 video solutions for Number of People Aware of a Secret, a medium level problem involving Dynamic Programming, Queue, Simulation. This walkthrough by codestorywithMIK has 14,211 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
On day 1, one person discovers a secret.
You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.
Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 6, delay = 2, forget = 4 Output: 5 Explanation: Day 1: Suppose the first person is named A. (1 person) Day 2: A is the only person who knows the secret. (1 person) Day 3: A shares the secret with a new person, B. (2 people) Day 4: A shares the secret with a new person, C. (3 people) Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people) Day 6: B shares the secret with E, and C shares the secret with F. (5 people)
Example 2:
Input: n = 4, delay = 1, forget = 3 Output: 6 Explanation: Day 1: The first person is named A. (1 person) Day 2: A shares the secret with B. (2 people) Day 3: A and B share the secret with 2 new people, C and D. (4 people) Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)
Constraints:
2 <= n <= 10001 <= delay < forget <= nProblem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming Simulation | O(n) | O(n) | Best for clarity and interviews when modeling day-by-day state transitions |
| Optimized Sliding Window / Constant Space | O(n) | O(1) | When memory usage matters or you want a cleaner rolling-window sharer count |