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 <= nThe key challenge in #2327 Number of People Aware of a Secret is to track how information spreads over multiple days while respecting two rules: a person can start sharing the secret only after a given delay, and they forget it after forget days. A practical way to solve this is by using Dynamic Programming combined with a sliding window or queue-based simulation.
Instead of tracking each individual separately, we maintain a DP array where dp[i] represents the number of people who learn the secret on day i. From there, we simulate how many people are eligible to share the secret on future days while removing those who forget it. Efficient implementations maintain a running count of active sharers, avoiding nested loops.
This approach ensures the simulation runs efficiently even for large n. With proper state tracking, the algorithm runs in O(n) time while using O(n) space to store daily counts.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Sliding Window / Queue Simulation | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Let dp[i][j] be the number of people who have known the secret for exactly j + 1 days, at day i.
If j > 0, dp[i][j] = dp[i – 1][j – 1].
dp[i][0] = sum(dp[i – 1][j]) for j in [delay – 1, forget – 2].
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving dynamic programming with simulation or sliding windows are common in FAANG-style interviews. This question tests a candidate’s ability to model time-based state transitions and optimize naive simulations.
A dynamic programming array combined with a sliding window or queue-like tracking works best. This structure helps keep track of when people start sharing the secret and when they forget it, enabling efficient updates each day.
The optimal approach uses Dynamic Programming to track how many people learn the secret on each day. By maintaining a sliding window of active sharers between the delay and forget limits, the algorithm efficiently simulates the spread without checking every person individually.
Dynamic programming helps store the number of people who learn the secret on each day and reuse that information for future days. Since the sharing process depends on earlier days, DP naturally models this time-based dependency.