Grumpy Bookstore Owner

🎯

Grumpy Bookstore Owner

mediumSLIDING_WINDOWAmazonGoogle

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.

💡 This problem is a classic example of using a sliding window to optimize a fixed-size segment within an array. Beginners often struggle to combine a base calculation with a variable window gain, which is key here.

📋

Problem Statement

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

💡

Example

Input"customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3"

Output16

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.

• All grumpy values are 0 → output is sum of all customers
• All grumpy values are 1 → output is max sum of any X-length window
• X equals n → output is sum of all customers
• customers array contains zeros → ensure no division or invalid assumptions

⚠️

Common Mistakes

Not separating base satisfaction and extra gain

Incorrect total satisfaction calculation

✅ Always sum customers where grumpy=0 separately before adding window gain

Off-by-one errors in sliding window boundaries

Wrong window sums or index out of bounds

✅ Carefully use inclusive/exclusive indices and test edge cases

Recomputing window sums from scratch each time

Inefficient O(n*X) solution leading to TLE

✅ Use sliding window technique to update sums incrementally

Not handling the case when X equals n

Incorrect output or index errors

✅ Ensure loops and windows handle full array size correctly

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every possible window, even though it's inefficient.

Intuition

Calculate the base satisfied customers (when owner is not grumpy) and then try every possible X-minute window to convert grumpy minutes to happy, summing the additional customers gained.

Algorithm

1. Calculate total customers satisfied without any technique (sum customers where grumpy=0).
2. For each possible window of size X, calculate extra customers gained by converting grumpy minutes to happy.
3. Keep track of the maximum extra customers gained.
4. Return the sum of base satisfied customers and maximum extra customers.

💡 The nested loops make it hard to see efficiency, but this approach guarantees correctness by exhaustive checking.

</>

Code

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
    max_extra = 0
    for start in range(n - X + 1):
        extra = 0
        for i in range(start, start + X):
            if grumpy[i] == 1:
                extra += customers[i]
        if extra > max_extra:
            max_extra = extra
    return base_satisfied + max_extra

# Driver code
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: 16

Line Notes

base_satisfied = 0Initialize base satisfied customers count to accumulate customers when owner is not grumpy

if grumpy[i] == 0:Add customers only when owner is not grumpy to base satisfaction

for start in range(n - X + 1):Try every possible window of size X to find maximum extra customers

if grumpy[i] == 1:Count extra customers only if owner is grumpy in this window

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int n = customers.length;
        int baseSatisfied = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                baseSatisfied += customers[i];
            }
        }
        int maxExtra = 0;
        for (int start = 0; start <= n - X; start++) {
            int extra = 0;
            for (int i = start; i < start + X; i++) {
                if (grumpy[i] == 1) {
                    extra += customers[i];
                }
            }
            if (extra > maxExtra) {
                maxExtra = extra;
            }
        }
        return baseSatisfied + maxExtra;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] customers = {1,0,1,2,1,1,7,5};
        int[] grumpy = {0,1,0,1,0,1,0,1};
        int X = 3;
        System.out.println(sol.maxSatisfied(customers, grumpy, X)); // Expected: 16
    }
}

Line Notes

int baseSatisfied = 0;Initialize base satisfied customers count to accumulate customers when owner is not grumpy

if (grumpy[i] == 0)Add customers only when owner is not grumpy to base satisfaction

for (int start = 0; start <= n - X; start++)Try every possible window of size X to find maximum extra customers

if (grumpy[i] == 1)Count extra customers only if owner is grumpy in this window

#include <iostream>
#include <vector>
using namespace std;

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
    int n = customers.size();
    int baseSatisfied = 0;
    for (int i = 0; i < n; i++) {
        if (grumpy[i] == 0) {
            baseSatisfied += customers[i];
        }
    }
    int maxExtra = 0;
    for (int start = 0; start <= n - X; start++) {
        int extra = 0;
        for (int i = start; i < start + X; i++) {
            if (grumpy[i] == 1) {
                extra += customers[i];
            }
        }
        if (extra > maxExtra) {
            maxExtra = extra;
        }
    }
    return baseSatisfied + maxExtra;
}

int main() {
    vector<int> customers = {1,0,1,2,1,1,7,5};
    vector<int> grumpy = {0,1,0,1,0,1,0,1};
    int X = 3;
    cout << maxSatisfied(customers, grumpy, X) << endl; // Expected: 16
    return 0;
}

Line Notes

int baseSatisfied = 0;Initialize base satisfied customers count to accumulate customers when owner is not grumpy

if (grumpy[i] == 0)Add customers only when owner is not grumpy to base satisfaction

for (int start = 0; start <= n - X; start++)Try every possible window of size X to find maximum extra customers

if (grumpy[i] == 1)Count extra customers only if owner is grumpy in this window

function maxSatisfied(customers, grumpy, X) {
    const n = customers.length;
    let baseSatisfied = 0;
    for (let i = 0; i < n; i++) {
        if (grumpy[i] === 0) {
            baseSatisfied += customers[i];
        }
    }
    let maxExtra = 0;
    for (let start = 0; start <= n - X; start++) {
        let extra = 0;
        for (let i = start; i < start + X; i++) {
            if (grumpy[i] === 1) {
                extra += customers[i];
            }
        }
        if (extra > maxExtra) {
            maxExtra = extra;
        }
    }
    return baseSatisfied + maxExtra;
}

// Test
const customers = [1,0,1,2,1,1,7,5];
const grumpy = [0,1,0,1,0,1,0,1];
const X = 3;
console.log(maxSatisfied(customers, grumpy, X)); // Expected: 16

Line Notes

let baseSatisfied = 0;Initialize base satisfied customers count to accumulate customers when owner is not grumpy

if (grumpy[i] === 0)Add customers only when owner is not grumpy to base satisfaction

for (let start = 0; start <= n - X; start++)Try every possible window of size X to find maximum extra customers

if (grumpy[i] === 1)Count extra customers only if owner is grumpy in this window

⏱

Complexity

TimeO(n * X)

SpaceO(1)

For each of the n-X+1 windows, we sum up to X elements, resulting in O(n*X) time.

💡 If n=10^5 and X=10^5, this means up to 10^10 operations, which is too slow for interviews.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and correctness.

🧠

Sliding Window (Prefix Sum + Window Scan)

💡 This approach improves efficiency by precomputing the base satisfaction and then using a sliding window to find the best window to convert grumpy minutes.

Intuition

Calculate base satisfaction from non-grumpy minutes, then slide a window of size X over the array to find the maximum extra customers gained by converting grumpy minutes within that window.

Algorithm

1. Calculate base satisfaction from all non-grumpy minutes.
2. Create an array extra where extra[i] = customers[i] if grumpy[i] == 1 else 0.
3. Use a sliding window of size X over extra to find the maximum sum of extra customers.
4. Return base satisfaction plus the maximum extra sum found.

💡 Sliding window avoids repeated summation by adding the new element and removing the old one as the window moves.

</>

Code

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    extra = [0] * n
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
        else:
            extra[i] = customers[i]
    window_sum = sum(extra[:X])
    max_extra = window_sum
    for i in range(X, n):
        window_sum += extra[i] - extra[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

# Driver code
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: 16

Line Notes

extra = [0] * nInitialize array to hold extra customers from grumpy minutes

if grumpy[i] == 0:Add to base satisfaction if owner is not grumpy

window_sum = sum(extra[:X])Calculate initial window sum for first X elements

window_sum += extra[i] - extra[i - X]Slide window by adding new element and removing old

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int n = customers.length;
        int baseSatisfied = 0;
        int[] extra = new int[n];
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                baseSatisfied += customers[i];
            } else {
                extra[i] = customers[i];
            }
        }
        int windowSum = 0;
        for (int i = 0; i < X; i++) {
            windowSum += extra[i];
        }
        int maxExtra = windowSum;
        for (int i = X; i < n; i++) {
            windowSum += extra[i] - extra[i - X];
            if (windowSum > maxExtra) {
                maxExtra = windowSum;
            }
        }
        return baseSatisfied + maxExtra;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] customers = {1,0,1,2,1,1,7,5};
        int[] grumpy = {0,1,0,1,0,1,0,1};
        int X = 3;
        System.out.println(sol.maxSatisfied(customers, grumpy, X)); // Expected: 16
    }
}

Line Notes

int[] extra = new int[n];Array to store extra customers from grumpy minutes

if (grumpy[i] == 0)Add to base satisfaction if owner is not grumpy

for (int i = 0; i < X; i++)Calculate initial window sum for first X elements

windowSum += extra[i] - extra[i - X];Slide window by adding new and removing old element

#include <iostream>
#include <vector>
using namespace std;

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
    int n = customers.size();
    int baseSatisfied = 0;
    vector<int> extra(n, 0);
    for (int i = 0; i < n; i++) {
        if (grumpy[i] == 0) {
            baseSatisfied += customers[i];
        } else {
            extra[i] = customers[i];
        }
    }
    int windowSum = 0;
    for (int i = 0; i < X; i++) {
        windowSum += extra[i];
    }
    int maxExtra = windowSum;
    for (int i = X; i < n; i++) {
        windowSum += extra[i] - extra[i - X];
        if (windowSum > maxExtra) {
            maxExtra = windowSum;
        }
    }
    return baseSatisfied + maxExtra;
}

int main() {
    vector<int> customers = {1,0,1,2,1,1,7,5};
    vector<int> grumpy = {0,1,0,1,0,1,0,1};
    int X = 3;
    cout << maxSatisfied(customers, grumpy, X) << endl; // Expected: 16
    return 0;
}

Line Notes

vector<int> extra(n, 0);Initialize vector to hold extra customers from grumpy minutes

if (grumpy[i] == 0)Add to base satisfaction if owner is not grumpy

for (int i = 0; i < X; i++)Calculate initial window sum for first X elements

windowSum += extra[i] - extra[i - X];Slide window by adding new and removing old element

function maxSatisfied(customers, grumpy, X) {
    const n = customers.length;
    let baseSatisfied = 0;
    const extra = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (grumpy[i] === 0) {
            baseSatisfied += customers[i];
        } else {
            extra[i] = customers[i];
        }
    }
    let windowSum = 0;
    for (let i = 0; i < X; i++) {
        windowSum += extra[i];
    }
    let maxExtra = windowSum;
    for (let i = X; i < n; i++) {
        windowSum += extra[i] - extra[i - X];
        if (windowSum > maxExtra) {
            maxExtra = windowSum;
        }
    }
    return baseSatisfied + maxExtra;
}

// Test
const customers = [1,0,1,2,1,1,7,5];
const grumpy = [0,1,0,1,0,1,0,1];
const X = 3;
console.log(maxSatisfied(customers, grumpy, X)); // Expected: 16

Line Notes

const extra = new Array(n).fill(0);Initialize array to hold extra customers from grumpy minutes

if (grumpy[i] === 0)Add to base satisfaction if owner is not grumpy

for (let i = 0; i < X; i++)Calculate initial window sum for first X elements

windowSum += extra[i] - extra[i - X];Slide window by adding new and removing old element

⏱

Complexity

TimeO(n)

SpaceO(n)

We do a single pass to compute base and extra arrays, then a sliding window pass over extra, each O(n).

💡 For n=10^5, this means about 2*10^5 operations, which is efficient for interviews.

Interview Verdict: Accepted / Efficient

This approach is efficient and practical for large inputs, suitable for coding interviews.

🧠

Sliding Window (Space Optimized)

💡 We can optimize space by not storing the extra array explicitly, instead calculating the window sum on the fly.

Intuition

Calculate base satisfaction as before, then use a sliding window over the original arrays, adding customers[i] when grumpy[i] == 1 inside the window, updating sums as the window moves.

Algorithm

1. Calculate base satisfaction from non-grumpy minutes.
2. Initialize window sum for first X minutes by summing customers where grumpy=1.
3. Slide the window from start to end, updating the window sum by adding new grumpy customers and removing old ones.
4. Track the maximum window sum and return base satisfaction plus this maximum.

💡 This approach saves memory by using variables instead of arrays, while maintaining O(n) time.

</>

Code

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
    window_sum = 0
    for i in range(X):
        if grumpy[i] == 1:
            window_sum += customers[i]
    max_extra = window_sum
    for i in range(X, n):
        if grumpy[i] == 1:
            window_sum += customers[i]
        if grumpy[i - X] == 1:
            window_sum -= customers[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

# Driver code
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: 16

Line Notes

if grumpy[i] == 0:Add to base satisfaction only when owner is not grumpy

for i in range(X):Initialize window sum for first X minutes

if grumpy[i] == 1:Add customers to window sum only if owner is grumpy

window_sum -= customers[i - X]Remove customers leaving the window if owner was grumpy

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int n = customers.length;
        int baseSatisfied = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                baseSatisfied += customers[i];
            }
        }
        int windowSum = 0;
        for (int i = 0; i < X; i++) {
            if (grumpy[i] == 1) {
                windowSum += customers[i];
            }
        }
        int maxExtra = windowSum;
        for (int i = X; i < n; i++) {
            if (grumpy[i] == 1) {
                windowSum += customers[i];
            }
            if (grumpy[i - X] == 1) {
                windowSum -= customers[i - X];
            }
            if (windowSum > maxExtra) {
                maxExtra = windowSum;
            }
        }
        return baseSatisfied + maxExtra;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] customers = {1,0,1,2,1,1,7,5};
        int[] grumpy = {0,1,0,1,0,1,0,1};
        int X = 3;
        System.out.println(sol.maxSatisfied(customers, grumpy, X)); // Expected: 16
    }
}

Line Notes

if (grumpy[i] == 0)Add to base satisfaction only when owner is not grumpy

for (int i = 0; i < X; i++)Initialize window sum for first X minutes

if (grumpy[i] == 1)Add customers to window sum only if owner is grumpy

windowSum -= customers[i - X];Remove customers leaving the window if owner was grumpy

#include <iostream>
#include <vector>
using namespace std;

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
    int n = customers.size();
    int baseSatisfied = 0;
    for (int i = 0; i < n; i++) {
        if (grumpy[i] == 0) {
            baseSatisfied += customers[i];
        }
    }
    int windowSum = 0;
    for (int i = 0; i < X; i++) {
        if (grumpy[i] == 1) {
            windowSum += customers[i];
        }
    }
    int maxExtra = windowSum;
    for (int i = X; i < n; i++) {
        if (grumpy[i] == 1) {
            windowSum += customers[i];
        }
        if (grumpy[i - X] == 1) {
            windowSum -= customers[i - X];
        }
        if (windowSum > maxExtra) {
            maxExtra = windowSum;
        }
    }
    return baseSatisfied + maxExtra;
}

int main() {
    vector<int> customers = {1,0,1,2,1,1,7,5};
    vector<int> grumpy = {0,1,0,1,0,1,0,1};
    int X = 3;
    cout << maxSatisfied(customers, grumpy, X) << endl; // Expected: 16
    return 0;
}

Line Notes

if (grumpy[i] == 0)Add to base satisfaction only when owner is not grumpy

for (int i = 0; i < X; i++)Initialize window sum for first X minutes

if (grumpy[i] == 1)Add customers to window sum only if owner is grumpy

windowSum -= customers[i - X];Remove customers leaving the window if owner was grumpy

function maxSatisfied(customers, grumpy, X) {
    const n = customers.length;
    let baseSatisfied = 0;
    for (let i = 0; i < n; i++) {
        if (grumpy[i] === 0) {
            baseSatisfied += customers[i];
        }
    }
    let windowSum = 0;
    for (let i = 0; i < X; i++) {
        if (grumpy[i] === 1) {
            windowSum += customers[i];
        }
    }
    let maxExtra = windowSum;
    for (let i = X; i < n; i++) {
        if (grumpy[i] === 1) {
            windowSum += customers[i];
        }
        if (grumpy[i - X] === 1) {
            windowSum -= customers[i - X];
        }
        if (windowSum > maxExtra) {
            maxExtra = windowSum;
        }
    }
    return baseSatisfied + maxExtra;
}

// Test
const customers = [1,0,1,2,1,1,7,5];
const grumpy = [0,1,0,1,0,1,0,1];
const X = 3;
console.log(maxSatisfied(customers, grumpy, X)); // Expected: 16

Line Notes

if (grumpy[i] === 0)Add to base satisfaction only when owner is not grumpy

for (let i = 0; i < X; i++)Initialize window sum for first X minutes

if (grumpy[i] === 1)Add customers to window sum only if owner is grumpy

windowSum -= customers[i - X];Remove customers leaving the window if owner was grumpy

⏱

Complexity

TimeO(n)

SpaceO(1)

We only use variables and a single pass through the arrays, so time is O(n) and space is constant.

💡 This is the most efficient approach in both time and space, ideal for interviews.

Interview Verdict: Accepted / Optimal

This approach is optimal and should be coded in interviews after explaining the intuition.

📊

All Approaches - One-Glance Tradeoffs

💡 The sliding window with space optimization is best for interviews; brute force is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * X)	O(1)	No	N/A	Mention only - never code
2. Sliding Window with Extra Array	O(n)	O(n)	No	N/A	Good for explaining optimization
3. Sliding Window Space Optimized	O(n)	O(1)	No	N/A	Code this in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Optimize to sliding window with extra array and explain the improvement.Further optimize space by computing window sums on the fly.Code the optimal solution carefully and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your ability to identify the sliding window pattern, optimize nested loops, and write clean, efficient code.

Common Follow-ups

• What if the owner can choose multiple windows? → Use interval scheduling or DP.
• What if X varies dynamically? → Consider prefix sums and binary search.

💡 These follow-ups test your ability to extend the problem and adapt your solution.

🔍

Pattern Recognition

When to Use

1) Problem involves a fixed-size window or segment; 2) Need to optimize sum or count within that window; 3) Base calculation plus window gain; 4) Constraints require O(n) or better solution.

Signature Phrases

continuous window of size Xmaximum number of customers satisfiedowner is grumpy or not

NOT This Pattern When

Problems requiring variable window sizes or complex state transitions are different patterns.

Similar Problems

Maximum Sum Subarray of Size K - similar fixed window sum optimizationLongest Substring Without Repeating Characters - sliding window for substring constraints

Practice

1. Consider the following code snippet implementing the optimal sliding window approach for longest substring with at most k distinct characters. What is the returned value when calling length_of_longest_substring_k_distinct('aabbcc', 2)?

easy

A. 6

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace window expansion and last_seen updates

   For 'aabbcc' with k=2, the longest substring with at most 2 distinct chars is 'aabb' or 'bbcc', length 4.

2. Step 2: Confirm max_length calculation

   max_length updates to 4 when window covers 'aabb' or 'bbcc'. The function returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest valid substring length is 4 [OK]

Hint: Longest substring with 2 distinct chars in 'aabbcc' is length 4 [OK]

Common Mistakes:

• Off-by-one errors counting substring length
• Confusing distinct character count when shrinking window

2. 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

3. What is the time complexity of the sliding window approach for the Minimum Size Subarray Sum problem, and why might some candidates incorrectly think it is O(n²)?

medium

A. O(n log n) due to sorting or binary search inside the loop

B. O(n²) because of nested loops implied by two pointers

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n) but with O(n) auxiliary space for prefix sums

Solution

1. Step 1: Identify pointer movements

   Right pointer moves forward once per iteration; left pointer moves forward only when shrinking window, each element visited at most twice.

2. Step 2: Analyze total operations

   Since both pointers only move forward, total operations are proportional to 2n = O(n), no nested repeated scanning.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window is classic O(n) approach [OK]

Hint: Two pointers each move forward once -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing prefix sums with sliding window
• Thinking auxiliary space affects time complexity

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 the problem is modified so that the subarray size k can vary, and you want to find the maximum sum subarray of any size between 1 and k. Which approach correctly adapts the sliding window technique to handle this variant efficiently?

hard

A. Use the original fixed-size sliding window for each size from 1 to k and take the maximum result; total time O(n*k).

B. Use a variable-size sliding window that expands and contracts dynamically to find maximum sums for all sizes up to k in O(n) time.

C. Use a prefix sum array and check all subarrays of sizes 1 to k in O(n*k) time without sliding window.

D. Use a max-heap to store sums of all subarrays of sizes 1 to k and extract the maximum in O(n log n) time.

Solution

1. Step 1: Understand the problem variant

   We want the maximum sum subarray for any size from 1 to k, not just fixed size k.

2. Step 2: Evaluate approaches

   Variable-size sliding window (B) is not straightforward here because the problem requires fixed-size subarrays for each size. Prefix sums (C) and max-heap (D) are less efficient or more complex. Running fixed-size sliding window for each size from 1 to k is simple and correct, with O(n*k) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window repeated for each size from 1 to k -> O(n*k) [OK]

Hint: Sliding window works per fixed size; varying sizes require repeated runs [OK]

Common Mistakes:

• Assuming variable-size sliding window can handle all sizes in O(n)
• Ignoring increased complexity of varying window sizes
• Using complex data structures unnecessarily