Number of People Aware of a Secret

attempt 1

My first solution was really stupid.

I initially treated the problem like a sliding window with two halves. The first half are people that discovered the secret delay days ago and are able to share the secret. The second half are people that recently discovered the secret and are NOT able to share the secret.

My algorithm uses a circular array to reduce space complexity, and iterates over the people who can share the secret to calculate how many new people learn it each day.

Exemplar table below:

DAY||1|2|3|4|4|5|6|7|8|
---|-------------------
   ||0 0|0 1|
   | 0|0 0|1 0|
   | 0 0|0 1|0 1|
   | 0 0 0|1 0|1 1|
   | 0 0 0 1|0 1|1 1|
   | 0 0 0 1 0|1 1|1 2|

code

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        int start = 1;
        vector<long long> days(forget+1, 0);
        int size = days.size();
        days[forget-1] = 1;

        for (int i = 0; i < n-1; ++i) {
            long long sum = 0;
            int index = start;

            for (int j = 0; j < forget - delay; ++j) {
                sum = (sum + days[index]) % MOD;
                index = (index + 1) % size;
            }
            index = (index + delay - 1) % size;
            days[index] = sum;

            start = (start + 1) % size;
        }
        long long ans = 0;
        start = (size + start - 1) % size;
        for (int i = 0; i < forget; ++i) {
            ans = (ans + days[start]) % MOD;
            start = (start + 1) % size;
        }
        return ans;
    }
private:
    int MOD = 1e9+7;
};

complexity

• Time: O(n^2)
• Space: O(n)

attempt 2

My second attempt makes a lot more sense. Now, we have a dp array instead, and we let it keep track of how many people learn about the secret on a given day.

Initially, on day 1, exactly one person knows the secret so dp[1] = 1.

vector<long long> dp (n+1, 0);
dp[1] = 1;

Then we maintain a share variable to keep track of the number of people sharing the secret on a given day.

int share = 0;

Now, on each day, we update the share variable:

• we check dp[max(i - delay, 0)] and add it to share since these people are learning about the secret
• we check dp[max(i - forget, 0)] and subtract it from share since these people are forgetting about the secret

for (int i = 2; i <= n; ++i) {
    dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + MOD) % MOD;
}

Afterwards, we can simply go back, iterate through the last forget days and sum up all the values to get the ans.

int ans = 0;
for (int i = n - forget + 1; i <= n; ++i) {
    ans = (ans + dp[i]) % MOD;
}
return ans;

code

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<long long> dp (n+1, 0);
        dp[1] = 1;
        int share = 0;

        for (int i = 2; i <= n; ++i) {
            dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + MOD) % MOD;
        }

        int ans = 0;
        for (int i = n - forget + 1; i <= n; ++i) {
            ans = (ans + dp[i]) % MOD;
        }
        return ans;
    }
private:
    const int MOD = 1e9+7;
};

complexity

• Time: O(n)
• Space: O(n)

time taken

• 67 minutes and 12 seconds
  • highkey i was just trolling- gain a trundle. your strongest trundle's ability no longer heals-