Grumpy Bookstore Owner

▶

Steps

setup

Calculate base satisfaction from non-grumpy minutes

We iterate over all minutes and sum customers where the owner is not grumpy (grumpy[i] == 0). This sum represents customers already satisfied without any technique.

💡 This step isolates the guaranteed satisfied customers, so we only need to optimize the grumpy intervals.

Line:

for i in range(n):
    if grumpy[i] == 0:
        base_satisfied += customers[i]

💡 Separating base satisfaction simplifies the problem to maximizing extra satisfaction from grumpy intervals.

setup

Base satisfaction after full scan

After scanning all minutes, base_satisfied is 10, summing customers at non-grumpy minutes: indices 0, 2, 4, and 6.

💡 Knowing the base satisfaction helps us measure how much extra satisfaction the technique can add.

Line:

base_satisfied = 10

💡 The base satisfaction is a fixed value; the sliding window will find the best extra satisfaction.

expand

Initialize window sum for first X=3 minutes

We sum customers in the first 3 minutes where the owner is grumpy (grumpy[i] == 1). Minutes 1 and 3 are grumpy with customers 0 and 2 respectively, minute 2 is not grumpy.

💡 This initializes the sliding window to measure extra satisfaction if technique is applied starting at minute 0.

Line:

for i in range(X):
    if grumpy[i] == 1:
        window_sum += customers[i]

💡 The window sum now represents extra customers satisfied if the technique is applied to the first 3 minutes.

setup

Set max_extra to initial window sum

We set max_extra to the current window sum of 2, representing the best extra satisfaction found so far.

💡 Tracking max_extra helps us remember the best window as we slide through the array.

Line:

max_extra = window_sum

💡 max_extra starts as the first window's extra satisfaction and will update if better windows are found.

expand

Slide window right: move right to 3, left to 1

We move the window right by one minute: add minute 3 (grumpy=1, customers=2) to window sum and remove minute 0 (grumpy=0, customers=1) which does not affect window sum.

💡 Sliding the window updates the extra satisfaction by including new grumpy customers and excluding old ones.

Line:

if grumpy[i] == 1:
    window_sum += customers[i]
if grumpy[i - X] == 1:
    window_sum -= customers[i - X]

💡 Window sum updates efficiently by adding and removing only grumpy customers at window boundaries.

record_answer

Update max_extra if current window sum is greater

Current window sum is 3, which is greater than max_extra 2, so we update max_extra to 3.

💡 We track the best window sum to maximize extra satisfaction.

Line:

if window_sum > max_extra:
    max_extra = window_sum

💡 The algorithm remembers the best window found so far.

expand

Slide window right: move right to 4, left to 2

Add minute 4 (grumpy=0, customers=1) to window sum only if grumpy, but grumpy[4]=0 so no addition. Remove minute 1 (grumpy=1, customers=0) from window sum.

💡 Window sum changes only by grumpy customers entering or leaving the window.

Line:

if grumpy[i] == 1:
    window_sum += customers[i]
if grumpy[i - X] == 1:
    window_sum -= customers[i - X]

💡 Window sum updates correctly even when grumpy customers have zero customers.

record_answer

Check if max_extra needs update

Current window sum is 3, equal to max_extra, so max_extra remains 3.

💡 We only update max_extra if the current window sum is strictly greater.

Line:

if window_sum > max_extra:
    max_extra = window_sum

💡 The algorithm keeps the best window sum found so far.

expand

Slide window right: move right to 5, left to 3

Add minute 5 (grumpy=1, customers=1) to window sum and remove minute 2 (grumpy=0, customers=1) which does not affect window sum.

💡 Window sum increases by customers at grumpy minute 5, reflecting potential extra satisfaction.

Line:

if grumpy[i] == 1:
    window_sum += customers[i]
if grumpy[i - X] == 1:
    window_sum -= customers[i - X]

💡 Window sum updates dynamically as the window slides.

record_answer

Update max_extra to new window sum

Current window sum is 4, which is greater than max_extra 3, so max_extra updates to 4.

💡 We track the best window sum to maximize extra satisfaction.

Line:

if window_sum > max_extra:
    max_extra = window_sum

💡 The algorithm finds a better window for extra satisfaction.

expand

Slide window right: move right to 6, left to 4

Add minute 6 (grumpy=0, customers=7) to window sum only if grumpy, but grumpy[6]=0 so no addition. Remove minute 3 (grumpy=1, customers=2) from window sum.

💡 Window sum decreases by customers at minute 3 as it leaves the window.

Line:

if grumpy[i] == 1:
    window_sum += customers[i]
if grumpy[i - X] == 1:
    window_sum -= customers[i - X]

💡 Window sum correctly reflects the new window after sliding.

record_answer

Check if max_extra needs update

Current window sum is 2, which is less than max_extra 4, so max_extra remains 4.

💡 We only update max_extra if the current window sum is strictly greater.

Line:

if window_sum > max_extra:
    max_extra = window_sum

💡 The algorithm keeps the best window sum found so far.

expand

Slide window right: move right to 7, left to 5

Add minute 7 (grumpy=1, customers=5) to window sum and remove minute 4 (grumpy=0, customers=1) which does not affect window sum.

💡 Window sum increases by customers at grumpy minute 7, reflecting potential extra satisfaction.

Line:

if grumpy[i] == 1:
    window_sum += customers[i]
if grumpy[i - X] == 1:
    window_sum -= customers[i - X]

💡 Window sum updates dynamically as the window slides.

record_answer

Update max_extra to new window sum

Current window sum is 7, which is greater than max_extra 4, so max_extra updates to 7.

💡 We track the best window sum to maximize extra satisfaction.

Line:

if window_sum > max_extra:
    max_extra = window_sum

💡 The algorithm finds the best window for extra satisfaction at the end of the array.

reconstruct

Calculate final answer by adding base satisfaction and max_extra

We add base_satisfied (10) and max_extra (7) to get the maximum total satisfied customers: 17.

💡 Combining base and extra satisfaction gives the final answer.

Line:

return base_satisfied + max_extra

💡 The final answer represents the maximum customers satisfied after applying the technique optimally.

def maxSatisfied(customers, grumpy, X):
    n = len(customers)  # STEP 1
    base_satisfied = 0  # STEP 1
    for i in range(n):  # STEP 1
        if grumpy[i] == 0:
            base_satisfied += customers[i]  # STEP 1
    window_sum = 0  # STEP 3
    for i in range(X):  # STEP 3
        if grumpy[i] == 1:
            window_sum += customers[i]  # STEP 3
    max_extra = window_sum  # STEP 4
    for i in range(X, n):  # STEP 5
        if grumpy[i] == 1:
            window_sum += customers[i]  # STEP 5
        if grumpy[i - X] == 1:
            window_sum -= customers[i - X]  # STEP 5
        if window_sum > max_extra:
            max_extra = window_sum  # STEP 6,10,14
    return base_satisfied + max_extra  # STEP 15

if __name__ == '__main__':
    customers = [1,0,1,2,1,1,7,5]
    grumpy = [0,1,0,1,0,1,0,1]
    X = 3
    print(maxSatisfied(customers, grumpy, X))  # Expected output: 17

📊

Grumpy Bookstore Owner - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how the sliding window technique optimizes the problem by focusing on only the grumpy intervals and how the window moves and updates the sums efficiently.

expand

L ▼

1

0

0

1

1

2

2

3

1

4

1

5

7

6

5

7

Metric: 0

Answer: 0

expand

L ▼

1

0

0

1

1

2

2

3

1

4

1

5

7

6

5

7

Metric: 0

Answer: 10

expand

L ▼

1

0

0

1

R ▼

1

2

2

3

1

4

1

5

7

6

5

7

Window: [1, 0, 1]

Metric: 2

Answer: 10

record_answer

L ▼

1

0

0

1

R ▼

1

2

2

3

1

4

1

5

7

6

5

7

Window: [1, 0, 1]

Metric: 2

Answer: 12

expand

1

0

L ▼

0

1

1

2

R ▼

2

3

1

4

1

5

7

6

5

7

Window: [0, 1, 2]

Metric: 3

Answer: 12

record_answer

1

0

L ▼

0

1

1

2

R ▼

2

3

1

4

1

5

7

6

5

7

Window: [0, 1, 2]

Metric: 3

Answer: 13

shrink

1

0

0

1

L ▼

1

2

2

3

R ▼

1

4

1

5

7

6

5

7

Window: [1, 2, 1]

Metric: 3

Answer: 13

record_answer

1

0

0

1

L ▼

1

2

2

3

R ▼

1

4

1

5

7

6

5

7

Window: [1, 2, 1]

Metric: 3

Answer: 13

expand

1

0

0

1

1

2

L ▼

2

3

1

4

R ▼

1

5

7

6

5

7

Window: [2, 1, 1]

Metric: 4

Answer: 13

record_answer

1

0

0

1

1

2

L ▼

2

3

1

4

R ▼

1

5

7

6

5

7

Window: [2, 1, 1]

Metric: 4

Answer: 14

shrink

1

0

0

1

1

2

2

3

L ▼

1

4

1

5

R ▼

7

6

5

7

Window: [1, 1, 7]

Metric: 2

Answer: 14

record_answer

1

0

0

1

1

2

2

3

L ▼

1

4

1

5

R ▼

7

6

5

7

Window: [1, 1, 7]

Metric: 2

Answer: 14

expand

1

0

0

1

1

2

2

3

1

4

L ▼

1

5

7

6

R ▼

5

7

Window: [1, 7, 5]

Metric: 7

Answer: 14

record_answer

1

0

0

1

1

2

2

3

1

4

L ▼

1

5

7

6

R ▼

5

7

Window: [1, 7, 5]

Metric: 7

Answer: 17

record_answer

1

0

0

1

1

2

2

3

1

4

L ▼

1

5

7

6

R ▼

5

7

Window: [1, 7, 5]

Metric: 7

Answer: 17

Key Takeaways

✓ Separating base satisfaction from extra satisfaction simplifies the problem.

It is hard to see from code alone that non-grumpy customers are always satisfied and can be summed upfront.

✓ Sliding window efficiently tracks extra satisfied customers by adding and removing only grumpy customers at window boundaries.

Visualizing each window move clarifies how the sum updates without recomputing from scratch.

✓ Tracking max_extra during window slides finds the optimal interval to apply the technique.

The decision to update max_extra is clearer when watching the window sums compared step-by-step.

Practice

1. Consider the following Python code implementing the sliding window with count matching optimization to find all anagrams of p in s. What is the final returned list when s = "cbaebabacd" and p = "abc"?

easy

A. [0, 1, 6]

B. [0, 6, 7]

C. [0, 6, 8]

D. [0, 6]

Solution

1. Step 1: Trace first window (indices 0 to 2)

   Substring "cba" is an anagram of "abc", so index 0 is added.

2. Step 2: Slide window and check matches

   Next valid anagram found at index 6 ("bac"). No other windows match all counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known example output matches [0, 6] [OK]

Hint: Anagrams appear at indices 0 and 6 only [OK]

Common Mistakes:

• Including indices where substring is not full anagram
• Off-by-one errors in window boundaries

2. You are given an integer array and a fixed window size k. The task is to find the contiguous subarray of length k that has the maximum average value. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window technique maintaining a running sum of the current window

B. Brute force nested loops checking all subarrays of size k

C. Dynamic programming with memoization of subproblems

D. Greedy approach selecting the largest elements regardless of position

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the maximum average of any contiguous subarray of fixed size k, which suggests examining all windows of size k.

2. Step 2: Identify optimal approach

   Sliding window maintains a running sum by adding the new element and removing the oldest, achieving O(n) time. Brute force is O(n*k), DP and greedy do not fit this fixed-size window problem optimally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in O(1) per step, total O(n) time [OK]

Hint: Sliding window updates sum in O(1) per step [OK]

Common Mistakes:

• Thinking greedy works without considering window contiguity
• Assuming DP is needed for fixed-size windows

3. What is the time complexity of the optimized sliding window algorithm that uses filtered characters for the minimum window substring problem, where n is the length of s and m is the length of t?

medium

A. O(n) because each character in s is visited at most twice by the two pointers

B. O(n * m) because for each character in s we check all characters in t

C. O(n + m) because we filter s and then slide over filtered characters

D. O(n^2) because shrinking and expanding the window can cause nested loops

Solution

1. Step 1: Identify main loops

   The algorithm uses two pointers moving over filtered characters, each pointer advances at most n times.

2. Step 2: Analyze filtering and counting

   Filtering s takes O(n), sliding window over filtered characters is O(n) since each character is visited twice max.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Confusing filtering cost
• Assuming nested loops cause O(n^2)
• Ignoring that each pointer moves only forward

4. What is the time complexity of the optimal sliding window algorithm that checks if s2 contains a permutation of s1, where n = len(s2) and m = len(s1)?

medium

A. O(n * m), because for each character in s2 we compare frequency maps of size m.

B. O(n), because the sliding window moves through s2 once with constant-time frequency updates.

C. O(n log m), due to sorting frequency arrays at each step.

D. O(m + n), since we initialize frequency counts and scan s2 once.

Solution

1. Step 1: Analyze outer loop over s2

   The sliding window moves from left to right over s2 exactly once, so this is O(n).

2. Step 2: Check frequency updates and comparisons

   Frequency counts are updated in O(1) time using fixed-size arrays of length 26 (alphabet size), and match count is updated incrementally without full map comparisons.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with constant-time updates -> O(n) [OK]

Hint: Frequency updates are O(1), sliding window moves once [OK]

Common Mistakes:

• Assuming frequency map comparison is O(m) each step
• Confusing initialization cost with per-iteration cost

5. Suppose you want to find the longest substring with at most k distinct characters, but now characters can be reused infinitely many times and the string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Use a frequency map with counts and shrink window when counts exceed k distinct characters, ignoring last seen positions

B. Maintain an ordered dictionary of last seen indices and shrink window as usual; no change needed

C. Use a frequency map and shrink the window only when distinct characters exceed k, ignoring last seen indices

D. Switch to a brute force approach since reuse breaks sliding window assumptions

Solution

1. Step 1: Understand reuse impact

   When characters can be reused infinitely, tracking last seen indices is insufficient; frequency counts are needed.

2. Step 2: Modify approach

   Use a frequency map to count occurrences and shrink window when distinct characters exceed k, ignoring last seen positions.

3. Step 3: Confirm efficiency

   This approach maintains O(n) time and handles reuse correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map with counts is required for reuse scenarios [OK]

Hint: Frequency counts needed when characters can be reused infinitely [OK]

Common Mistakes:

• Assuming last seen indices suffice for reuse
• Thinking brute force is necessary