1052. Grumpy Bookstore Owner

MediumView on LeetCode

Array Sliding Window

Time: O(n)

Space: O(1)

Intuition

Base satisfied = sum where grumpy[i]==0. Sliding window of size X for maximum extra customers from grumpy minutes.

Algorithm

1base = sum(customers[i] where grumpy[i]==0).
2Window of size X: extra = sum(customers[i] where grumpy[i]==1) in window.
3Return base + max(extra).

Common Pitfalls

•Only add grumpy-minute customers as extra (non-grumpy already in base).

1052.cs

// Approach: Add base satisfied customers, then find the sliding window of length 'minutes' that maximises extra customers recovered from grumpy minutes.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxSatisfied(int[] customers, int[] grumpy, int minutes)
    {
        int satisfied = 0, windowSatisfied = 0;
        int madeSatisfied = 0;

        for (int i = 0; i < customers.Length; i++)
        {
            if (grumpy[i] == 0)
                satisfied += customers[i];
            else
                windowSatisfied += customers[i];

            if (i >= minutes && grumpy[i - minutes] == 1)
                windowSatisfied -= customers[i - minutes];
            madeSatisfied = Math.Max(madeSatisfied, windowSatisfied);
        }

        return satisfied + madeSatisfied;
    }
}

Was this solution helpful?