Course4all
Join us on telegram
Home/dsa/Sliding Window/Grumpy Bookstore Owner

Grumpy Bookstore Owner

Master this topic with zero to advance depth.

Grumpy Bookstore Owner

A bookstore owner can be grumpy at certain minutes. You can use a 'secret technique' to keep them calm for minutes consecutive minutes. Maximize satisfied customers.

Visual Representation

customers = [1, 0, 1, 2, 1, 1, 7, 5] grumpy = [0, 1, 0, 1, 0, 1, 0, 1] minutes = 3 Base satisfaction (owner not grumpy): 1 + 1 + 1 + 7 = 10 Potential extra (using technique on window of size 3): Win [1, 2, 1] (mins 1-3) -> Extra: 0*c[1] + 1*c[2] + 0*c[3] = 2 Win [7, 5] (mins 6-7) -> ... finding max extra ...
Medium

Examples

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Approach 1

Level I: Brute Force

Intuition

Iterate through every possible starting minute i for the 'X-minute technique'. For each i, calculate the total satisfied customers by summing: (base satisfied customers) + (additional customers satisfied while the technique is active at i).

Thought Process

  1. Calculate BaseSatisfied: Sum of customers[j] where grumpy[j] == 0 for all j.
  2. Iterate through each possible start i from 0 to n - minutes.
  3. For each i, calculate Additional: Sum of customers[j] where grumpy[j] == 1 and i <= j < i + minutes.
  4. Max Score = BaseSatisfied + max(Additional).
⏱ O(N * minutes)💾 O(1)

Detailed Dry Run

StartBaseAdditionalTotal
0101+1+012
3102+1+114
5101+5+016 (MAX)
java
public class Main {
    public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length;
        int base = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }

        int maxAdditional = 0;
        for (int i = 0; i <= n - minutes; i++) {
            int currentAdditional = 0;
            for (int j = i; j < i + minutes; j++) {
                if (grumpy[j] == 1) currentAdditional += customers[j];
            }
            maxAdditional = Math.max(maxAdditional, currentAdditional);
        }
        return base + maxAdditional;
    }

    public static void main(String[] args) {
        int[] cust = {1,0,1,2,1,1,7,5};
        int[] grump = {0,1,0,1,0,1,0,1};
        System.out.println(maxSatisfied(cust, grump, 3)); // 16
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We want to choose a window of size minutes where we 'cancel' the owner's grumpiness to maximize additional customers. This is a classic fixed-size sliding window over the potential 'bonuses'.

Patterns

  1. Fixed Window: The technique duration is fixed at minutes.
  2. Additive Bonus: Base satisfied customers are always there; we only focus on maximizing the 'recovered' customers in a window.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowRecoveredMax Recovered
[1,0,1]00
[0,1,2]33
[1,2,1]33
[1,1,7]88 (MAX)
java
public class Main {
    public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int satisfied = 0, extra = 0, maxExtra = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) satisfied += customers[i];
            if (grumpy[i] == 1) extra += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) extra -= customers[i - minutes];
            maxExtra = Math.max(maxExtra, extra);
        }
        return satisfied + maxExtra;
    }

    public static void main(String[] args) {
        System.out.println(maxSatisfied(new int[]{1,0,1,2,1,1,7,5}, new int[]{0,1,0,1,0,1,0,1}, 3));
    }
}

⚠️ Common Pitfalls & Tips

Ensure you only add/remove customers[i] based on grumpy[i] == 1. The base customers grumpy[i] == 0 should not be affected by the sliding window logic after they are counted initially.

← Previous QuestionMinimum Operations to Reduce X to Zero
Next Question →Maximum Number of Vowels in a Substring of Given Length