LeetCode 2327 - Number of People Aware of a Secret

LeetCode Problem 2327

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Queue, Simulation

Solution

Problem Understanding

The problem describes how a secret spreads over time. On day 1, exactly one person knows the secret. Every person who learns the secret behaves according to two rules:

1. They must wait delay days before they can begin sharing the secret.
2. They forget the secret after forget days, and once they forget it, they can no longer share it.

Each eligible person shares the secret with exactly one new person every day.

The task is to determine how many people still know the secret at the end of day n.

The important detail is that a person can share the secret for a specific window of time. Suppose someone learns the secret on day d:

• They begin sharing on day d + delay
• They forget on day d + forget
• Therefore, they can share during the days:

[d + delay, d + forget - 1]

The answer counts everyone who still remembers the secret on day n, including people who learned it recently and have not yet started sharing.

The constraints are relatively small:

• 2 <= n <= 1000
• 1 <= delay < forget <= n

Because n is at most 1000, an O(n^2) dynamic programming solution is completely acceptable. However, a naive person-by-person simulation can still become unnecessarily complicated and inefficient.

Several edge cases are important:

• People may learn the secret very close to day n, meaning they never get a chance to share it.
• When delay = 1, sharing starts immediately on the next day, causing rapid exponential growth.
• When forget is only slightly larger than delay, people have a very short sharing window.
• A person who forgets the secret on a given day cannot share it on that same day.

Carefully handling the exact inclusive and exclusive day ranges is the key challenge of the problem.

Approaches

Brute Force Approach

A direct simulation approach would model every individual person separately.

Whenever someone learns the secret, we could store:

• The day they learned it
• The days they will share
• The day they forget

Then, for every day, we iterate through all existing people and determine:

• Whether they still remember the secret
• Whether they are currently allowed to share it

If they can share, we create a new person entry.

This approach is correct because it explicitly simulates the exact rules of the process. However, the number of people can grow extremely quickly, especially when delay = 1. In the worst case, the number of simulated individuals becomes exponential.

Even though n <= 1000, maintaining every person individually is inefficient and unnecessary.

Optimal Dynamic Programming Approach

The key insight is that we do not need to track individual people. Instead, we only need to know:

How many people first learned the secret on each day

Define:

dp[i] = number of people who learn the secret on day i

Now consider how people contribute to future days.

If someone learned the secret on day j, they will share it on days:

[j + delay, j + forget - 1]

That means on a future day i, every earlier day j contributes to dp[i] if:

j + delay <= i < j + forget

Equivalently:

i - forget < j <= i - delay

So, for each day i, we sum all people who are currently active sharers.

This transforms the problem into a clean dynamic programming process.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Simulates every individual separately
Optimal	O(n²)	O(n)	Tracks how many people learn the secret each day

Algorithm Walkthrough

1. Create a dynamic programming array dp of size n + 1.

dp[i] represents the number of people who first learn the secret on day i. 2. Initialize the starting condition.

On day 1, one person knows the secret:

dp[1] = 1

3. Process each future day from 2 to n.

For each day day, determine how many people are currently able to share the secret. 4. Iterate through all earlier days prev_day.

A person who learned the secret on prev_day can share on day if:

prev_day + delay <= day < prev_day + forget

5. If the condition is true, add dp[prev_day] to the number of new people learning the secret today.

Each eligible sharer creates exactly one new person. 6. Store the result in dp[day].

This gives the number of people who first discover the secret on that day. 7. After filling the DP array, compute the final answer.

A person still remembers the secret on day n if:

n - forget < learned_day <= n

8. Sum all dp[day] values for people who have not forgotten yet.
9. Return the result modulo 10^9 + 7.

Why it works

The algorithm works because every person is fully characterized by the day they first learned the secret. From that day, their sharing behavior is deterministic.

The DP transition correctly counts all people who are actively sharing on a given day, and each active sharer contributes exactly one newly informed person. Since every newly informed person is recorded exactly once in dp, no person is missed or double-counted.

The final summation correctly excludes anyone who has already forgotten the secret.

Python Solution

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7

        dp = [0] * (n + 1)
        dp[1] = 1

        for day in range(2, n + 1):
            total_new_people = 0

            for prev_day in range(1, day):
                if prev_day + delay <= day < prev_day + forget:
                    total_new_people += dp[prev_day]

            dp[day] = total_new_people % MOD

        answer = 0

        for day in range(1, n + 1):
            if day + forget > n:
                answer += dp[day]

        return answer % MOD

The implementation directly follows the dynamic programming strategy.

The dp array stores how many people first learn the secret on each day. The initialization dp[1] = 1 represents the original person.

For every future day, the code scans all previous days and checks whether those people are currently in their sharing window. The condition:

prev_day + delay <= day < prev_day + forget

ensures that:

• They have waited long enough to start sharing
• They have not forgotten yet

All eligible sharers contribute one new person each.

After computing all days, the final loop counts only people who still remember the secret on day n. Anyone whose forgetting day is after n is still counted.

Modulo arithmetic is used because the number of people can grow very large.

Go Solution

func peopleAwareOfSecret(n int, delay int, forget int) int {
    const MOD int = 1_000_000_007

    dp := make([]int, n+1)
    dp[1] = 1

    for day := 2; day <= n; day++ {
        totalNewPeople := 0

        for prevDay := 1; prevDay < day; prevDay++ {
            if prevDay+delay <= day && day < prevDay+forget {
                totalNewPeople += dp[prevDay]
                totalNewPeople %= MOD
            }
        }

        dp[day] = totalNewPeople
    }

    answer := 0

    for day := 1; day <= n; day++ {
        if day+forget > n {
            answer += dp[day]
            answer %= MOD
        }
    }

    return answer
}

The Go implementation is structurally identical to the Python version.

A slice is used instead of a Python list. Since Go integers can overflow in larger computations, modulo reduction is applied during accumulation. The logic for determining active sharers and final survivors remains exactly the same.

Worked Examples

Example 1

Input:

n = 6
delay = 2
forget = 4

We track dp[day].

Day	People Who Can Share	New People	dp State
1	None	1	[1]
2	None	0	[1,0]
3	Day 1 person	1	[1,0,1]
4	Day 1 person	1	[1,0,1,1]
5	Day 3 person	1	[1,0,1,1,1]
6	Day 3 and Day 4 people	2	[1,0,1,1,1,2]

Now determine who still remembers on day 6.

A person forgets after 4 days.

Learned On	Forget Day	Still Remembers?
1	5	No
3	7	Yes
4	8	Yes
5	9	Yes
6	10	Yes

Total:

1 + 1 + 1 + 2 = 5

Answer:

5

Example 2

Input:

n = 4
delay = 1
forget = 3

Day	People Who Can Share	New People	dp State
1	None	1	[1]
2	Day 1	1	[1,1]
3	Day 1 and Day 2	2	[1,1,2]
4	Day 2 and Day 3	3	[1,1,2,3]

Now count survivors on day 4.

Learned On	Forget Day	Still Remembers?
1	4	No
2	5	Yes
3	6	Yes
4	7	Yes

Total:

1 + 2 + 3 = 6

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each day, we scan all previous days
Space	O(n)	The DP array stores one value per day

The nested loops dominate the runtime. Since n <= 1000, an O(n²) solution performs comfortably within limits. The memory usage is linear because we only store the number of newly informed people for each day.

Test Cases

sol = Solution()

assert sol.peopleAwareOfSecret(6, 2, 4) == 5  # provided example 1
assert sol.peopleAwareOfSecret(4, 1, 3) == 6  # provided example 2

assert sol.peopleAwareOfSecret(2, 1, 2) == 1  # first person forgets quickly
assert sol.peopleAwareOfSecret(3, 1, 3) == 4  # rapid sharing growth
assert sol.peopleAwareOfSecret(5, 2, 3) == 2  # short sharing window
assert sol.peopleAwareOfSecret(10, 2, 5) > 0  # general medium case
assert sol.peopleAwareOfSecret(8, 3, 4) > 0  # delayed sharing
assert sol.peopleAwareOfSecret(15, 1, 15) > 0  # no one forgets before end
assert sol.peopleAwareOfSecret(20, 5, 6) > 0  # very narrow sharing interval
assert sol.peopleAwareOfSecret(1000, 1, 1000) > 0  # maximum constraint stress test

Test	Why
(6,2,4)	Validates provided example
(4,1,3)	Tests immediate sharing
(2,1,2)	Tests fast forgetting
(3,1,3)	Tests exponential growth behavior
(5,2,3)	Tests narrow sharing window
(10,2,5)	General correctness case
(8,3,4)	Tests long delay before sharing
(15,1,15)	Tests scenario where nobody forgets early
(20,5,6)	Tests minimal sharing duration
(1000,1,1000)	Stress test for upper constraints

Edge Cases

One important edge case occurs when delay = 1. In this scenario, every newly informed person can begin sharing immediately on the next day. This causes the number of people to grow very rapidly. A naive recursive simulation could become extremely inefficient. The DP solution handles this naturally because it only tracks counts per day rather than individual people.

Another tricky case occurs when forget = delay + 1. Here, people have only one day during which they are allowed to share the secret. Off-by-one mistakes are common in this situation. The condition:

prev_day + delay <= day < prev_day + forget

correctly models the inclusive start and exclusive end of the sharing window.

A final important edge case occurs near the end of the timeline. Some people may learn the secret shortly before day n and never get a chance to share it. These people must still be counted in the final answer because they remember the secret. The implementation handles this by summing all people whose forgetting day is strictly after n.