Grumpy Bookstore Owner

📋

Problem

Imagine a bookstore owner who is sometimes grumpy and sometimes happy. When grumpy, customers leave unhappy, but the owner can choose a window of time to be extra nice and improve customer satisfaction.

You are given two integer arrays customers and grumpy, both of length n, and an integer X. customers[i] is the number of customers entering the bookstore at minute i. grumpy[i] is 1 if the bookstore owner is grumpy at minute i, and 0 otherwise. When the owner is grumpy, customers leave unhappy and do not contribute to satisfaction. You can choose a continuous window of size X minutes during which the owner will not be grumpy, even if grumpy[i] is 1. Return the maximum number of customers that can be satisfied throughout the day by choosing the best window.

1 ≤ n ≤ 10^51 ≤ X ≤ n0 ≤ customers[i] ≤ 1000grumpy[i] is either 0 or 1

Edge cases: All grumpy values are 0 → output is sum of all customersAll grumpy values are 1 → output is max sum of any X-length windowX equals n → output is sum of all customers

</>

IDE

def maxSatisfied(customers: list[int], grumpy: list[int], X: int) -> int:public int maxSatisfied(int[] customers, int[] grumpy, int X)int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int X)function maxSatisfied(customers, grumpy, X)

def maxSatisfied(customers, grumpy, X):
    # Write your solution here
    pass

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int X) {
    // Write your solution here
    return 0;
}

function maxSatisfied(customers, grumpy, X) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 10Only summing base satisfaction without adding max extra from the chosen window.✅ Add sliding window logic to find max extra customers from grumpy minutes and add to base satisfaction.

Wrong: 0Failing on empty input or zero window size by returning default zero without checks.✅ Add explicit checks for empty arrays and zero X to return 0 safely.

Wrong: 14Ignoring base satisfaction and returning only max extra customers from window.✅ Sum all non-grumpy customers first, then add max extra from sliding window.

Wrong: 13Greedy approach picking wrong window, missing max extra customers.✅ Use sliding window to check all windows of size X and pick maximum sum.

Wrong: TLEUsing brute force nested loops O(n*X) for large inputs.✅ Implement O(n) sliding window approach to pass performance constraints.

✓

Test Cases

Try testing your solution on empty and minimal inputs to catch base cases.

Consider tricky inputs that break greedy or partial solutions.

Think about time complexity and how to optimize nested loops.

t1_01basic

Input{"customers":[1,0,1,2,1,1,7,5],"grumpy":[0,1,0,1,0,1,0,1],"X":3}

Expected16

⏱ Performance - must finish in 2000ms

Without using the technique, satisfied customers are at minutes with grumpy=0: 1 + 1 + 1 + 7 = 10. Using the technique on minutes 5 to 7 (1,7,5), we add 6 more customers who would otherwise be unsatisfied, total 16.

💡 Consider the base satisfaction from non-grumpy minutes plus extra from a chosen window.

💡 Use a sliding window of size X to find the max extra customers gained by suppressing grumpiness.

💡 Calculate base satisfaction first, then slide window to add max extra from grumpy minutes.

Why it failed: Incorrect total satisfaction: likely missed adding base satisfied customers or incorrectly summed extra customers in the window. Fix by summing all non-grumpy customers first, then add max extra from a sliding window over grumpy customers.

✓ Correctly computed base satisfaction plus maximum extra customers from the chosen window.

t1_02basic

Input{"customers":[4,10,10],"grumpy":[1,1,0],"X":2}

Expected24

⏱ Performance - must finish in 2000ms

Base satisfaction from non-grumpy minute 2 is 10. Using the technique on minutes 0 to 1 (4,10), we add 14 more customers, total 24.

💡 Identify base satisfaction from non-grumpy minutes first.

💡 Slide a window of size X over grumpy minutes to find max extra customers.

💡 Add base satisfaction to max extra customers from the window for final answer.

Why it failed: Wrong output due to ignoring base satisfaction or incorrect window sum. Fix by summing all non-grumpy customers first, then add max sum of grumpy customers in any X-length window.

✓ Correctly combined base satisfaction and maximum extra customers from the window.

t2_01edge

Input{"customers":[],"grumpy":[],"X":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty input arrays and zero window size means no customers and no satisfaction.

💡 Check behavior when input arrays are empty.

💡 Ensure code handles n=0 and X=0 without errors.

💡 Return 0 when no customers exist.

Why it failed: Code crashes or returns non-zero for empty input or zero window size. Fix by adding base case checks for empty arrays and zero X.

✓ Correctly returns 0 for empty input and zero window size.

t2_02edge

Input{"customers":[5],"grumpy":[0],"X":1}

Expected5

⏱ Performance - must finish in 2000ms

Single element with owner not grumpy means all customers are satisfied.

💡 Test single element input where grumpy is 0.

💡 Base satisfaction equals customers since no grumpiness.

💡 Window size equals array length, so total satisfaction is customers[0].

Why it failed: Fails single element case by ignoring base satisfaction or mishandling window size. Fix by correctly summing non-grumpy customers and handling single element arrays.

✓ Correctly handles single element with no grumpiness.

t2_03edge

Input{"customers":[1,2,3,4,5],"grumpy":[1,1,1,1,1],"X":5}

Expected15

⏱ Performance - must finish in 2000ms

All grumpy and window size equals n means all customers can be satisfied by using the technique on entire array.

💡 Consider when X equals n and all grumpy are 1.

💡 Base satisfaction is zero since all grumpy.

💡 Max extra is sum of entire customers array.

Why it failed: Incorrect output by not handling X == n or summing entire array for max extra. Fix by returning sum of all customers when X equals n.

✓ Correctly returns sum of all customers when X equals n and all grumpy.

t3_01corner

Input{"customers":[1,2,3,4,5],"grumpy":[1,0,1,0,1],"X":2}

Expected11

⏱ Performance - must finish in 2000ms

Base satisfaction from non-grumpy minutes 1 and 3 is 2 + 4 = 6. Max extra from any 2-length contiguous window covering grumpy minutes is 6 (window covering minutes 0 and 1: 1 + 2). Total 12.

💡 Beware of greedy approach that picks only first or last window.

💡 Use sliding window to check all possible windows of size X.

💡 Sum base satisfaction plus max extra from any window for correct answer.

Why it failed: Fails due to greedy approach picking wrong window, missing max extra customers. Fix by checking all contiguous windows of size X with sliding window technique.

✓ Correctly finds max extra customers by sliding window, avoiding greedy trap.

t3_02corner

Input{"customers":[3,8,5,1,7],"grumpy":[1,1,1,1,1],"X":3}

Expected16

⏱ Performance - must finish in 2000ms

All grumpy, base satisfaction 0. Max sum of any 3-length window is 16 (minutes 0 to 2: 3+8+5=16, minutes 1 to 3: 8+5+1=14, minutes 2 to 4: 5+1+7=13). Total 16.

💡 Check that you are not confusing 0/1 knapsack with this fixed window problem.

💡 Calculate max sum of any X-length window over grumpy customers.

💡 Return base satisfaction plus max extra customers from that window.

Why it failed: Incorrect output due to confusing problem with unbounded knapsack or summing incorrectly. Fix by using sliding window to find max sum of any X-length window over grumpy customers.

✓ Correctly computes max sum of any X-length window over grumpy customers.

t3_03corner

Input{"customers":[2,2,2,2,2],"grumpy":[1,1,1,1,1],"X":1}

Expected2

⏱ Performance - must finish in 2000ms

All grumpy, base satisfaction 0. Max sum of any 1-length window is 2, so total 2.

💡 Test smallest window size with all grumpy customers.

💡 Sliding window of size 1 is just max single element.

💡 Return base satisfaction plus max single grumpy customer.

Why it failed: Fails by summing multiple elements or ignoring window size 1. Fix by correctly handling window size 1 as max single element.

✓ Correctly handles window size 1 by picking max single grumpy customer.

t4_01performance

Input{"customers":[1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0,1000,500,1000,0],"grumpy":[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],"X":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and X=50. O(n*X) brute force will time out; efficient O(n) sliding window required.

💡 Brute force O(n*X) will time out for large n and X.

💡 Use sliding window technique to achieve O(n) time complexity.

💡 Precompute base satisfaction and slide window to find max extra efficiently.

Why it failed: TLE due to nested loops O(n*X). Fix by implementing O(n) sliding window approach.

✓ Efficient O(n) sliding window approach confirmed by passing performance test.

Practice

1. Given the following code snippet, what is the output when calling numSubarraysWithSum([1,0,1], 2)?

easy

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: Trace atMost(2)

   Right=0: current_sum=1 ≤2, count=1; Right=1: current_sum=1 ≤2, count=1+2=3; Right=2: current_sum=2 ≤2, count=3+3=6

2. Step 2: Trace atMost(1)

   Right=0: current_sum=1 ≤1, count=1; Right=1: current_sum=1 ≤1, count=1+2=3; Right=2: current_sum=2 >1, shrink window: current_sum=1, left=1, count=3+2=5

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   numSubarraysWithSum = 6 - 5 = 1 [BUG]

Hint: Subtract atMost(goal-1) from atMost(goal) to get exact count [OK]

Common Mistakes:

• Miscounting subarrays when shrinking window
• Off-by-one errors in count increments
• Confusing atMost(goal) with exact count

2. You are given a string and need to find the length of the longest substring where no character repeats. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings and verifying uniqueness by sorting each substring

B. Sliding window with a hash map tracking the last seen index of each character to dynamically adjust the window

C. Dynamic programming by storing longest substring lengths ending at each index without duplicates

D. Greedy approach by always extending the substring until a duplicate is found, then restarting from next character

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring without repeating characters, which suggests a variable-size window to track unique characters efficiently.

2. Step 2: Evaluate approaches

   Brute force and greedy approaches either have high time complexity or fail to adjust the window correctly. Dynamic programming is not straightforward here. The sliding window with a hash map efficiently tracks last seen indices and adjusts the window in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with index tracking is the known optimal pattern [OK]

Hint: Sliding window with index map -> O(n) solution [OK]

Common Mistakes:

• Confusing greedy restart with sliding window
• Using DP without clear state definition

3. Consider the following Python code implementing the optimal solution for the problem. What is the returned value when calling longestOnes([1,0,1,0], 1)?

from collections import deque

def longestOnes(nums, k):
    zero_positions = deque()
    left = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_positions.append(right)
        if len(zero_positions) > k:
            left = zero_positions.popleft() + 1
        max_length = max(max_length, right - left + 1)
    return max_length

easy

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace iterations with input [1,0,1,0], k=1

   Right=0: nums[0]=1, zero_positions=[], max_length=1 Right=1: nums[1]=0, zero_positions=[1], max_length=2 Right=2: nums[2]=1, zero_positions=[1], max_length=3 Right=3: nums[3]=0, zero_positions=[1,3], length=2 > k=1 triggers left update left = zero_positions.popleft()+1 = 1+1=2, zero_positions=[3], max_length remains 3

2. Step 2: Final max_length after loop ends is 3

   The longest subarray with at most 1 zero flipped is length 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual trace confirms max_length=3 [OK]

Hint: Track zero positions and window boundaries carefully [OK]

Common Mistakes:

• Off-by-one errors in window length
• Not updating left pointer correctly
• Confusing max_length update timing

4. Given the following code and input cardPoints = [4, 2, 3, 1], k = 2, what is the value of min_subarray_sum after the loop finishes?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate initial sums

   n=4, k=2, window_size=2, current_sum=sum([4,2])=6, min_subarray_sum=6

2. Step 2: Iterate over the array

   i=2: current_sum=6 + 3 - 4 = 5, min_subarray_sum=5
   i=3: current_sum=5 + 1 - 2 = 4, min_subarray_sum=4

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimum subarray sum found is 4 after sliding window moves [OK]

Hint: Sliding window updates sum by adding new and removing old element [OK]

Common Mistakes:

• Off-by-one error in loop range
• Incorrect initial window sum
• Not updating min_subarray_sum correctly

5. Consider the following buggy code for counting binary subarrays with sum equal to goal. Which line contains the subtle bug that causes incorrect counts for subarrays starting at index 0?

def numSubarraysWithSum(nums, goal):
    def atMost(S):
        count = left = 0
        current_sum = 0
        for right, num in enumerate(nums):
            current_sum += num
            while current_sum > S:
                current_sum -= nums[left]
                left += 1
            count += right - left
        return count
    return atMost(goal) - atMost(goal - 1) if goal > 0 else atMost(0)

medium

A. Line 10: The count increment uses 'right - left' instead of 'right - left + 1'.

B. Line 4: Initialization of count and left variables.

C. Line 7: The while loop condition should be 'current_sum >= S' instead of '>'.

D. Line 12: The return statement incorrectly handles the case when goal is zero.

Solution

1. Step 1: Identify count increment logic

   Count should include the current subarray length: number of subarrays ending at right is 'right - left + 1'. Using 'right - left' misses subarrays starting at left.

2. Step 2: Understand impact on subarrays starting at index 0

   Missing '+1' causes undercounting subarrays that start exactly at index 0, leading to incorrect total counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct count increment is 'right - left + 1' [OK]

Hint: Count subarrays ending at right as 'right - left + 1' [OK]

Common Mistakes:

• Off-by-one errors in count increments
• Misunderstanding while loop condition
• Incorrect handling of goal=0 case