16-Grumpy-Bookstore-Owner.md

Grumpy Bookstore Owner

Problem Link

https://leetcode.com/problems/grumpy-bookstore-owner/

---

Pattern

• Sliding Window

---

Approach

Calculate base satisfied customers, then find window of size minutes where grumpy owner converts maximum unhappy customers.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int base = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }
        int extra = 0;
        for (int i = 0; i < minutes; i++) {
            if (grumpy[i] == 1) extra += customers[i];
        }
        int maxExtra = extra;
        for (int i = minutes; i < customers.length; i++) {
            if (grumpy[i] == 1) extra += customers[i];
            if (grumpy[i-minutes] == 1) extra -= customers[i-minutes];
            maxExtra = Math.max(maxExtra, extra);
        }
        return base + maxExtra;
    }
}