Coding Interview PatternsGrumpy Bookstore Owner
MediumSliding Window

Grumpy Bookstore Owner

Explanation & Solution

Practice Problem

Description

A bookstore owner has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array nums where nums[i] is the number of customers that enter at the start of the ith minute, and an integer array grumpy where grumpy[i] is 1 if the owner is grumpy during minute i, and 0 otherwise.

When the owner is not grumpy, the customers are satisfied. When the owner is grumpy, the customers arriving during that minute are not satisfied.

The owner knows a secret technique to suppress grumpiness for minutes consecutive minutes, making all customers during that window satisfied.

Return the maximum number of satisfied customers after using the technique optimally.

Examples

Input:nums = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
0
1
1
0
2
1
3
2
4
1
5
1
6
7
7
5
0
0
1
1
2
0
3
1
4
0
5
1
6
0
7
1

Output: 16

Explanation: The owner uses the technique on the last 3 minutes (indices 5, 6, 7). Always-satisfied customers (grumpy=0): indices 0,2,4,6 → 1+1+1+7 = 10. Extra from suppressing grumpiness at indices 5 and 7: 1+5 = 6. Total = 16.

Input:nums = [1], grumpy = [0], minutes = 1
0
1
0
0

Output: 1

Explanation: The customer is already satisfied since the owner is not grumpy.

Input:nums = [4,10,10], grumpy = [1,1,0], minutes = 2
0
4
1
10
2
10
0
1
1
1
2
0

Output: 24

Explanation: Always-satisfied: index 2 → 10. Use technique on indices 0,1 → extra 4+10 = 14. Total = 24.

Constraints

  • n == nums.length == grumpy.length
  • 1 <= n <= 2 * 10^4
  • 0 <= nums[i] <= 1000
  • grumpy[i] is 0 or 1
  • 1 <= minutes <= n

Approach

Sliding Window pattern

1. Count Always-Satisfied Customers

Iterate through the array and sum up nums[i] for every index where grumpy[i] === 0. These customers are satisfied regardless of where we apply the technique.

2. Build the Initial Window

Compute the extra customers we would gain by suppressing grumpiness for the first minutes indices. Only count nums[i] where grumpy[i] === 1, since non-grumpy minutes are already counted.

3. Slide the Window

Move the window one position at a time from left to right. For each step:

  • Add the new right element's contribution (only if grumpy[i] === 1).
  • Remove the old left element's contribution (only if grumpy[i - minutes] === 1).
  • Track the maximum extra gained across all window positions.

4. Combine the Results

The answer is alwaysSatisfied + maxExtra — the base satisfied customers plus the best possible gain from the suppression technique.

Key Insight

By separating the problem into two parts — always-satisfied customers and the optimal gain from the suppression window — we reduce it to a simple fixed-size sliding window problem. We only need to track the sum of grumpy-minute customers within the window, making the solution O(n) time and O(1) space.

Visualization

Input:
[1, 0, 1, 2, 1, 1, 7, 5], minutes = 3
1001122314157657
—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone
7 steps

Solution Code

Previous
Maximum Number of Vowels in a Substring of Given Length
Next
Get Equal Substrings Within Budget