How do you solve Number of People Aware of a Secret on LeetCode?

Number of People Aware of a Secret (LeetCode #2327) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The delay and forget parameters create a time window for sharing and forgetting the secret.

What is the brute force solution for Number of People Aware of a Secret?

The brute force approach for Number of People Aware of a Secret is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach simulates each day, tracking how many people know the secret and when they start sharing it. It checks each person to see if they can share the secret based on their delay and forget time. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of People Aware of a Secret?

Number of People Aware of a Secret uses the following concepts: Dynamic Programming, Queue, Simulation. The recommended patterns to study are: Dynamic Programming, Simulation.

What are the interview tips for Number of People Aware of a Secret?

Always clarify the problem constraints and edge cases before jumping into coding. Think about how to optimize your solution after writing the brute force version. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Number of People Aware of a Secret?

Not properly handling the modulo operation, which can lead to incorrect results. Failing to account for the days when people forget the secret.

#2327

Number of People Aware of a Secret

Medium

Dynamic ProgrammingQueueSimulationDynamic ProgrammingSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a dynamic programming approach to track how many people know the secret on each day, leveraging the relationships between days to avoid redundant calculations.

⚙️

Algorithm

3 steps

1Step 1: Initialize an array to keep track of the number of people who know the secret on each day.
2Step 2: For each day, calculate how many new people can learn the secret based on those who learned it in previous days.
3Step 3: Sum the number of people who still remember the secret at the end of day n.

solution.py14 lines

1# Full working Python code
2MOD = 10**9 + 7
3def peopleAwareOfSecret(n, delay, forget):
4    people = [0] * (n + 1)
5    people[1] = 1
6    for day in range(1, n + 1):
7        if day + delay <= n:
8            people[day + delay] = (people[day + delay] + people[day]) % MOD
9        if day + forget <= n:
10            people[day + forget] = (people[day + forget] - people[day]) % MOD
11    result = sum(people[max(1, n - forget + 1):]) % MOD
12    return result
13
14print(peopleAwareOfSecret(6, 2, 4))

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the days once, and each day involves a constant amount of work. The space complexity is O(n) due to the array used to track the number of people.

1The delay and forget parameters create a time window for sharing and forgetting the secret.
2Dynamic programming allows us to efficiently track the number of people who can share the secret without redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.