Grumpy Bookstore Owner - Practice Coding Problems

Grumpy Bookstore Owner - Problem

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 customers that enter the store at the start of the i^th 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 i^th minute, and 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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Base satisfied customers: 0 (index 1) + 1 (index 4) = 1. Apply technique to minutes 1-3: gain 0+1+2 = 3 additional. Total = 1 + 3 = 4.

Example 2 — Technique at Start

$ Input: customers = [1], grumpy = [0], minutes = 1

› Output: 1

💡 Note: Owner is naturally not grumpy, so 1 customer is already satisfied. Using technique doesn't change anything.

Example 3 — All Grumpy

$ Input: customers = [2,3,1], grumpy = [1,1,1], minutes = 2

› Output: 5

💡 Note: Base satisfied: 0 (all grumpy). Best technique window covers first 2 minutes: gain 2+3 = 5. Total = 0 + 5 = 5.

Constraints

1 ≤ customers.length == grumpy.length ≤ 2 × 10⁴
0 ≤ customers[i] ≤ 1000
grumpy[i] is either 0 or 1
1 ≤ minutes ≤ customers.length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

customers=[1,0,1,2,1], grumpy=[1,0,1,1,0], minutes=3

Find Optimal Window

Test where 3-minute technique yields most additional satisfied customers

Calculate Result

Base satisfaction + technique bonus = maximum total

Key Takeaway

🎯 Key Insight: Apply the technique to the window containing the most grumpy customers with highest values

Asked in

a Amazon 12 G Google 8 M Microsoft 6

The sliding window approach is optimal. Key insight: calculate base satisfied customers first, then use a sliding window to find the consecutive period where the technique adds maximum value. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Windows	O(n × minutes)	O(1)	Try applying the technique to every possible consecutive window of minutes
Sliding Window Optimization	O(n)	O(1)	Calculate base satisfaction once, then use sliding window to find best technique placement

Brute Force - Try All Windows — Algorithm Steps

For each possible starting position i from 0 to n-minutes
Apply technique to window [i, i+minutes-1]
Count total satisfied customers for this configuration
Keep track of maximum satisfied customers

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Window at Position 0

Apply technique to first 'minutes' positions

Try Window at Position 1

Slide window right and recalculate total

Continue Until End

Test all positions and return maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* customers, int* grumpy, int n, int minutes) {
    int maxSatisfied = 0;
    
    // Try each possible window position
    for (int start = 0; start <= n - minutes; start++) {
        int totalSatisfied = 0;
        
        // Count satisfied customers for this window configuration
        for (int i = 0; i < n; i++) {
            if (i >= start && i < start + minutes) {
                // Within technique window - all customers satisfied
                totalSatisfied += customers[i];
            } else if (grumpy[i] == 0) {
                // Outside window but owner not grumpy
                totalSatisfied += customers[i];
            }
            // If outside window and grumpy, customers not satisfied (add 0)
        }
        
        if (totalSatisfied > maxSatisfied) {
            maxSatisfied = totalSatisfied;
        }
    }
    
    return maxSatisfied;
}

int parseArray(char* line, int* arr) {
    int count = 0;
    char* token = strtok(line, "[],");
    while (token != NULL) {
        arr[count++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    return count;
}

int main() {
    char line1[1000], line2[1000], line3[100];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    fgets(line3, sizeof(line3), stdin);
    
    int customers[100], grumpy[100];
    int n = parseArray(line1, customers);
    parseArray(line2, grumpy);
    int minutes = atoi(line3);
    
    int result = solution(customers, grumpy, n, minutes);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × minutes)

For each of n-minutes+1 possible windows, we scan the entire array of length n

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track counts, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Windows — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler