1052. Grumpy Bookstore Owner - Explanation

Description

There is a bookstore owner that has a store open for n minutes. You are given an integer array customers of length n where customers[i] is the number of the customers that enter the store at the start of the ith minute and all those customers leave after the end of that minute.

During certain minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers entering during that minute are not satisfied. Otherwise, they are satisfied.

The bookstore owner knows a secret technique to remain not grumpy for minutes consecutive minutes, but this technique can only be used once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

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

Output: 16

Explanation:

The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Example 2:

Input: customers = [10,1,7], grumpy = [0,0,0], minutes = 2

Output: 18

Explanation: The bookstore owner is already not grumpy for all the customers.

Constraints:

n == customers.length == grumpy.length
1 <= minutes <= n <= 20,000
0 <= customers[i] <= 1000
grumpy[i] is either 0 or 1.

Topics

Array Sliding Window

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window - Maintaining a fixed-size window that slides across an array while tracking window properties
Array Traversal - Iterating through arrays while maintaining running sums and tracking maximum values

1. Brute Force

Intuition

Customers are satisfied when the owner is not grumpy. The owner can use a secret technique to suppress grumpiness for a consecutive window of minutes. We want to find the best position for this window to maximize total satisfied customers.

The idea is straightforward: first count all customers who are already satisfied (when grumpy is 0), then try every possible window position and see how many additional customers we can save by suppressing grumpiness during that window.

Algorithm

Calculate the baseline satisfaction by summing customers at all indices where the owner is not grumpy.
For each possible starting position of the technique window (from 0 to n - minutes):
- Count how many customers would be saved within this window (customers at grumpy minutes).
- Track the maximum total satisfaction (baseline + saved customers).
Return the maximum satisfaction found.

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        res, n = 0, len(customers)
        for i in range(n):
            if not grumpy[i]:
                res += customers[i]

        satisfied = res
        for i in range(n - minutes + 1):
            cur = 0
            for j in range(i, i + minutes):
                if grumpy[j]:
                    cur += customers[j]
            res = max(res, satisfied + cur)

        return res

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int res = 0, n = customers.length;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                res += customers[i];
            }
        }

        int satisfied = res;
        for (int i = 0; i <= n - minutes; i++) {
            int cur = 0;
            for (int j = i; j < i + minutes; j++) {
                if (grumpy[j] == 1) {
                    cur += customers[j];
                }
            }
            res = Math.max(res, satisfied + cur);
        }

        return res;
    }
}

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int res = 0, n = customers.size();
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                res += customers[i];
            }
        }

        int satisfied = res;
        for (int i = 0; i <= n - minutes; i++) {
            int cur = 0;
            for (int j = i; j < i + minutes; j++) {
                if (grumpy[j] == 1) {
                    cur += customers[j];
                }
            }
            res = max(res, satisfied + cur);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} customers
     * @param {number[]} grumpy
     * @param {number} minutes
     * @return {number}
     */
    maxSatisfied(customers, grumpy, minutes) {
        let res = 0, n = customers.length;
        for (let i = 0; i < n; i++) {
            if (grumpy[i] === 0) {
                res += customers[i];
            }
        }

        let satisfied = res;
        for (let i = 0; i <= n - minutes; i++) {
            let cur = 0;
            for (let j = i; j < i + minutes; j++) {
                if (grumpy[j] === 1) {
                    cur += customers[j];
                }
            }
            res = Math.max(res, satisfied + cur);
        }

        return res;
    }
}

public class Solution {
    public int MaxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int res = 0, n = customers.Length;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                res += customers[i];
            }
        }

        int satisfied = res;
        for (int i = 0; i <= n - minutes; i++) {
            int cur = 0;
            for (int j = i; j < i + minutes; j++) {
                if (grumpy[j] == 1) {
                    cur += customers[j];
                }
            }
            res = Math.Max(res, satisfied + cur);
        }

        return res;
    }
}

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    res, n := 0, len(customers)
    for i := 0; i < n; i++ {
        if grumpy[i] == 0 {
            res += customers[i]
        }
    }

    satisfied := res
    for i := 0; i <= n-minutes; i++ {
        cur := 0
        for j := i; j < i+minutes; j++ {
            if grumpy[j] == 1 {
                cur += customers[j]
            }
        }
        if satisfied+cur > res {
            res = satisfied + cur
        }
    }

    return res
}

class Solution {
    fun maxSatisfied(customers: IntArray, grumpy: IntArray, minutes: Int): Int {
        var res = 0
        val n = customers.size
        for (i in 0 until n) {
            if (grumpy[i] == 0) {
                res += customers[i]
            }
        }

        val satisfied = res
        for (i in 0..n - minutes) {
            var cur = 0
            for (j in i until i + minutes) {
                if (grumpy[j] == 1) {
                    cur += customers[j]
                }
            }
            res = maxOf(res, satisfied + cur)
        }

        return res
    }
}

class Solution {
    func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ minutes: Int) -> Int {
        var res = 0
        let n = customers.count
        for i in 0..<n {
            if grumpy[i] == 0 {
                res += customers[i]
            }
        }

        let satisfied = res
        for i in 0...(n - minutes) {
            var cur = 0
            for j in i..<(i + minutes) {
                if grumpy[j] == 1 {
                    cur += customers[j]
                }
            }
            res = max(res, satisfied + cur)
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$

Where $n$ is the size of the input array and $m$ is the number of minutes.

2. Sliding Window

Intuition

Instead of recalculating the saved customers for each window position from scratch, we can use a sliding window to efficiently update the count. As the window moves one position to the right, we add the contribution of the new element entering the window and remove the contribution of the element leaving.

This reduces redundant computation since we only need to track customers at grumpy minutes within the current window.

Algorithm

Initialize two counters: satisfied for customers already happy (non-grumpy minutes) and window for customers saved within the current window.
Use two pointers l and r to represent the sliding window boundaries.
For each position r:
- If grumpy at r, add those customers to the window count.
- Otherwise, add them to the baseline satisfied count.
- If the window exceeds minutes, shrink from the left by removing contributions at l (only if grumpy).
- Track the maximum window value seen.
Return satisfied + maxWindow.

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        l = 0
        window = max_window = 0
        satisfied = 0

        for r in range(len(customers)):
            if grumpy[r]:
                window += customers[r]
            else:
                satisfied += customers[r]

            if r - l + 1 > minutes:
                if grumpy[l]:
                    window -= customers[l]
                l += 1

            max_window = max(window, max_window)

        return satisfied + max_window

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int l = 0, window = 0, maxWindow = 0, satisfied = 0;

        for (int r = 0; r < customers.length; r++) {
            if (grumpy[r] == 1) {
                window += customers[r];
            } else {
                satisfied += customers[r];
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] == 1) {
                    window -= customers[l];
                }
                l++;
            }

            maxWindow = Math.max(window, maxWindow);
        }

        return satisfied + maxWindow;
    }
}

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int l = 0, window = 0, maxWindow = 0, satisfied = 0;

        for (int r = 0; r < customers.size(); r++) {
            if (grumpy[r] == 1) {
                window += customers[r];
            } else {
                satisfied += customers[r];
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] == 1) {
                    window -= customers[l];
                }
                l++;
            }

            maxWindow = max(window, maxWindow);
        }

        return satisfied + maxWindow;
    }
};

class Solution {
    /**
     * @param {number[]} customers
     * @param {number[]} grumpy
     * @param {number} minutes
     * @return {number}
     */
    maxSatisfied(customers, grumpy, minutes) {
        let l = 0, window = 0, maxWindow = 0, satisfied = 0;

        for (let r = 0; r < customers.length; r++) {
            if (grumpy[r] === 1) {
                window += customers[r];
            } else {
                satisfied += customers[r];
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] === 1) {
                    window -= customers[l];
                }
                l++;
            }

            maxWindow = Math.max(window, maxWindow);
        }

        return satisfied + maxWindow;
    }
}

public class Solution {
    public int MaxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int l = 0, window = 0, maxWindow = 0, satisfied = 0;

        for (int r = 0; r < customers.Length; r++) {
            if (grumpy[r] == 1) {
                window += customers[r];
            } else {
                satisfied += customers[r];
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] == 1) {
                    window -= customers[l];
                }
                l++;
            }

            maxWindow = Math.Max(window, maxWindow);
        }

        return satisfied + maxWindow;
    }
}

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    l, window, maxWindow, satisfied := 0, 0, 0, 0

    for r := 0; r < len(customers); r++ {
        if grumpy[r] == 1 {
            window += customers[r]
        } else {
            satisfied += customers[r]
        }

        if r-l+1 > minutes {
            if grumpy[l] == 1 {
                window -= customers[l]
            }
            l++
        }

        if window > maxWindow {
            maxWindow = window
        }
    }

    return satisfied + maxWindow
}

class Solution {
    fun maxSatisfied(customers: IntArray, grumpy: IntArray, minutes: Int): Int {
        var l = 0
        var window = 0
        var maxWindow = 0
        var satisfied = 0

        for (r in customers.indices) {
            if (grumpy[r] == 1) {
                window += customers[r]
            } else {
                satisfied += customers[r]
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] == 1) {
                    window -= customers[l]
                }
                l++
            }

            maxWindow = maxOf(window, maxWindow)
        }

        return satisfied + maxWindow
    }
}

class Solution {
    func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ minutes: Int) -> Int {
        var l = 0
        var window = 0
        var maxWindow = 0
        var satisfied = 0

        for r in 0..<customers.count {
            if grumpy[r] == 1 {
                window += customers[r]
            } else {
                satisfied += customers[r]
            }

            if r - l + 1 > minutes {
                if grumpy[l] == 1 {
                    window -= customers[l]
                }
                l += 1
            }

            maxWindow = max(window, maxWindow)
        }

        return satisfied + maxWindow
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Counting Already-Satisfied Customers in the Window

A common mistake is including customers who are already satisfied (when grumpy[i] = 0) in the window's "saved" count. The technique only helps during grumpy minutes, so only customers at indices where grumpy[i] = 1 should be added to the window sum. Counting non-grumpy customers in the window leads to double-counting since they are already part of the baseline satisfaction.

Off-by-One Errors in Window Boundaries

When implementing the sliding window, it is easy to miscalculate when to shrink the window. The window should have exactly minutes elements, so the condition should check if r - l + 1 > minutes before removing the left element. Using >= instead of > or forgetting to increment the left pointer after removal causes incorrect window sizes.

Forgetting to Track the Maximum Window Value

Some solutions correctly compute the window sum but forget to track the maximum value seen across all window positions. The final answer requires the best possible window, not just the last one computed. Always update maxWindow after each window adjustment to capture the optimal placement of the technique.