Skip to main content
Talentd

Number of People Aware of a Secret - Solution & Explanation

MediumDynamic ProgrammingQueueSimulation16 min readAsked at: Amazon, Microsoft, Google +3
Practice this problem

Problem Statement

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 <= 1000
  • 1 <= delay < forget <= n

Approach Overview

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.

Approach 1: Dynamic Programming Approach

This approach involves using a dynamic programming array to keep track of people who can start sharing the secret on a particular day. We'll calculate how many new people learn the secret each day and how many forget it. By maintaining a record of new sharers, we can update daily totals efficiently.

In this C solution, two arrays, dp and share, are used. dp[i] records the total count of people knowing the secret on day i. share[i] represents the count of people who are in their sharing period starting on day i. The iteration considers:

  • People who can start sharing after the delay period.
  • People who stop sharing after the forget period.
The function returns dp[n] as the final result modulo 10^9 + 7.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Optimized Constant Space Approach

This approach optimizes for space by not explicitly storing each day's state, retaining only necessary counters and calculating values iteratively. Instead of a long-term history, this method tracks incremental gains daily.

By using only an array with the size of 'forget', this Python function calculates the state of the secret sharers. The array acts as a rotating block capturing only necessary states of dp. The rolling calculation of total keeps the logic sound without needing a full recapture each day.

Code

Python

Python

Complexity

Time Complexity: O(n)
Space Complexity: O(forget)

Try this approach in the editor →

Approach 3: Difference Array

We use a difference array d[i] to record the change in the number of people who know the secret on day i, and an array cnt[i] to record the number of people who newly learn the secret on day i.

For the cnt[i] people who newly learn the secret on day i, they can share the secret with another cnt[i] people each day during the interval [i+delay, i+forget).

The answer is sum_{i=1}^{n} d[i].

The time complexity is O(n^2), and the space complexity is O(n), where n is the given integer.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n)
Space Complexity: O(n)

Optimized Constant Space Approach

Time Complexity: O(n)
Space Complexity: O(forget)

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming SimulationO(n)O(n)Best for clarity and interviews when modeling day-by-day state transitions
Optimized Sliding Window / Constant SpaceO(n)O(1)When memory usage matters or you want a cleaner rolling-window sharer count

Video Solution

Number of People Aware of a Secret | Recursion Memo | Bottom Up | Leetcode 2327 | codestorywithMIK • codestorywithMIK • 14,586 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of People Aware of a Secret easy or hard?
Number of People Aware of a Secret is classified as Medium difficulty. The challenge lies in modeling when people start sharing and when they forget, then maintaining the correct window of active sharers. Once the lifecycle is understood, the dynamic programming transition becomes straightforward.
Number of People Aware of a Secret Python/Java solution
Both Python and Java implementations follow the same DP recurrence. Maintain an array for people who learn the secret each day, update the active sharer count using delay and forget offsets, and compute values modulo 1e9+7. The algorithm runs in O(n) time and works easily across Python, Java, C++, and other languages.
How to solve Number of People Aware of a Secret in O(n)?
Maintain dp[i] as the number of people who learn the secret on day i. Track a running count of people allowed to share by adding dp[i - delay] when they become eligible and subtracting dp[i - forget] when they forget. The number of new learners each day equals the active sharer count, producing an O(n) dynamic programming solution.
What is the best approach for Number of People Aware of a Secret?
The most practical approach uses dynamic programming with a running count of active sharers. Track how many people learn the secret each day and update a sliding window of those who can share between delay and forget days. This gives an O(n) time solution with O(n) space while directly modeling the lifecycle of each group.
Is Number of People Aware of a Secret asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving lifecycle simulation and dynamic programming. Variants of spreading or expiring information frequently appear in interviews at companies like Amazon, Google, and Meta because they test window management and state transitions.
What data structure is used in Number of People Aware of a Secret?
Most solutions rely on a dynamic programming array combined with a sliding window or running sum. Some implementations conceptually treat the active sharers as a queue of groups entering and leaving the sharing window. These structures help efficiently track who can share on each day.
What is the time complexity of Number of People Aware of a Secret?
The optimal solution runs in O(n) time because each day from 1 to n is processed once. Updates only involve adding or removing groups entering or leaving the sharing window. Space complexity is O(n) with a DP array or O(1) with the optimized rolling-window version.

Ready to solve this problem?

Practice Number of People Aware of a Secret with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching