Number of People Aware of a Secret — LeetCode 2327 Python Solution

The problem

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.

Example

Input

n = 6, delay = 2, forget = 4

Output

5

Explanation

Day 1: Suppose the first person is named A. (1 person)

Python solution

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        m = (n << 1) + 10
        d = [0] * m
        cnt = [0] * m
        cnt[1] = 1
        for i in range(1, n + 1):
            if cnt[i]:
                d[i] += cnt[i]
                d[i + forget] -= cnt[i]
                nxt = i + delay
                while nxt < i + forget:
                    cnt[nxt] += cnt[i]
                    nxt += 1
        mod = 10**9 + 7
        return sum(d[: n + 1]) % mod

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2327. Number of People Aware of a Secret is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems