Maximum Average Subarray I

▶

Steps

setup

Initialize variables

We start by determining the length of the input array and creating a prefix sum array initialized with zeros.

💡 Setting up the prefix sum array is essential for efficient sum calculations later.

Line:

n = len(nums)
prefix = [0] * (n + 1)

💡 Prefix sum array length is one more than input array length to handle sums from start easily.

expand

Build prefix sum for index 0

Add the first element of nums to prefix sum array at index 1.

💡 Each prefix sum element stores the sum of all elements before it, enabling O(1) subarray sum queries.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=0

💡 prefix[1] = prefix[0] + nums[0] = 0 + 1 = 1

expand

Build prefix sum for index 1

Add the second element of nums to prefix sum array at index 2.

💡 Continuing to accumulate sums to enable quick subarray sum calculations.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=1

💡 prefix[2] = prefix[1] + nums[1] = 1 + 12 = 13

expand

Build prefix sum for index 2

Add the third element of nums to prefix sum array at index 3.

💡 Prefix sums continue to accumulate, including negative values.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=2

💡 prefix[3] = prefix[2] + nums[2] = 13 + (-5) = 8

expand

Build prefix sum for index 3

Add the fourth element of nums to prefix sum array at index 4.

💡 Prefix sums include more negative values, showing cumulative effect.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=3

💡 prefix[4] = prefix[3] + nums[3] = 8 + (-6) = 2

expand

Build prefix sum for index 4

Add the fifth element of nums to prefix sum array at index 5.

💡 Large positive number increases cumulative sum significantly.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=4

💡 prefix[5] = prefix[4] + nums[4] = 2 + 50 = 52

expand

Build prefix sum for index 5

Add the sixth element of nums to prefix sum array at index 6.

💡 Final prefix sum element completes the array.

Line:

prefix[i + 1] = prefix[i] + nums[i]  # i=5

💡 prefix[6] = prefix[5] + nums[5] = 52 + 3 = 55

setup

Initialize max_sum to negative infinity

Set max_sum to the smallest possible value to ensure any subarray sum will be larger.

💡 This allows the first subarray sum to update max_sum correctly.

Line:

max_sum = float('-inf')

💡 max_sum is ready to track the highest subarray sum found.

traverse

Evaluate subarray [0..3]

Calculate sum of first subarray of length k using prefix sums: prefix[4] - prefix[0] = 2 - 0 = 2.

💡 Prefix sums allow O(1) sum calculation for any subarray.

Line:

current_sum = prefix[i] - prefix[i - k]  # i=4

💡 First subarray sum sets initial max_sum.

traverse

Evaluate subarray [1..4]

Calculate sum of subarray from index 1 to 4: prefix[5] - prefix[1] = 52 - 1 = 51.

💡 Sliding window moves right by one, sum recalculated efficiently.

Line:

current_sum = prefix[i] - prefix[i - k]  # i=5

💡 New subarray sum is much larger, update max_sum and window position.

traverse

Evaluate subarray [2..5]

Calculate sum of subarray from index 2 to 5: prefix[6] - prefix[2] = 55 - 13 = 42.

💡 Window slides right again, sum recalculated quickly.

Line:

current_sum = prefix[i] - prefix[i - k]  # i=6

💡 Current subarray sum is less than max_sum, so no update.

reconstruct

Calculate and return maximum average

Divide max_sum by k to get the maximum average subarray value: 51 / 4 = 12.75.

💡 Final step converts sum to average as required by the problem.

Line:

return max_sum / k

💡 Maximum average subarray found efficiently using prefix sums and sliding window.

def findMaxAverage(nums, k):
    n = len(nums)  # STEP 1
    prefix = [0] * (n + 1)  # STEP 1
    for i in range(n):  # STEP 2-7
        prefix[i + 1] = prefix[i] + nums[i]  # STEP i+2
    max_sum = float('-inf')  # STEP 8
    for i in range(k, n + 1):  # STEP 9-11
        current_sum = prefix[i] - prefix[i - k]  # STEP i+8
        if current_sum > max_sum:  # STEP i+8
            max_sum = current_sum  # STEP i+8
    return max_sum / k  # STEP 12

if __name__ == '__main__':
    nums = [1,12,-5,-6,50,3]
    k = 4
    print(findMaxAverage(nums, k))  # Expected output: 12.75

📊

Maximum Average Subarray I - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how prefix sums enable constant-time subarray sum calculation and how the sliding window moves to find the maximum average efficiently.

expand

L=R

1

0

12

1

-5

2

-6

3

50

4

3

5

Metric: 0

expand

L=R

1

0

12

1

-5

2

-6

3

50

4

3

5

Metric: 1

expand

L ▼

1

0

R ▼

12

1

-5

2

-6

3

50

4

3

5

Metric: 13

expand

L ▼

1

0

12

1

R ▼

-5

2

-6

3

50

4

3

5

Metric: 8

expand

L ▼

1

0

12

1

-5

2

R ▼

-6

3

50

4

3

5

Metric: 2

expand

L ▼

1

0

12

1

-5

2

-6

3

R ▼

50

4

3

5

Metric: 52

expand

L ▼

1

0

12

1

-5

2

-6

3

50

4

R ▼

3

5

Metric: 55

record_answer

L=R

1

0

12

1

-5

2

-6

3

50

4

3

5

record_answer

L ▼

1

0

12

1

-5

2

R ▼

-6

3

50

4

3

5

Window: [1, 12, -5, -6]

Metric: 2

Answer: 2

record_answer

1

0

L ▼

12

1

-5

2

-6

3

R ▼

50

4

3

5

Window: [12, -5, -6, 50]

Metric: 51

Answer: 51

record_answer

1

0

12

1

L ▼

-5

2

-6

3

50

4

R ▼

3

5

Window: [-5, -6, 50, 3]

Metric: 42

Answer: 51

record_answer

1

0

L ▼

12

1

-5

2

-6

3

R ▼

50

4

3

5

Window: [12, -5, -6, 50]

Metric: 12.75

Answer: 12.75

Key Takeaways

✓ Prefix sums allow constant-time calculation of any fixed-length subarray sum.

Without prefix sums, summing each subarray would be O(k), making the algorithm slower.

✓ Sliding the window by one index and using prefix sums avoids redundant summations.

This shows how overlapping subarrays share computations, improving efficiency.

✓ Tracking max_sum and updating only when a larger sum is found ensures the correct maximum average.

This decision step is crucial to avoid missing the optimal subarray.

Practice

1. You are given an array of positive integers and a target sum. You need to find the length of the smallest contiguous subarray whose sum is at least the target. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking all subarrays

B. Sorting the array and using binary search for subarray sums

C. Dynamic programming with memoization over subarray sums

D. Sliding window with two pointers adjusting window size dynamically

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimal length subarray with sum ≥ target, which suggests a variable-size window approach.

2. Step 2: Identify algorithm that adjusts window size efficiently

   Sliding window with two pointers can expand and shrink the window in O(n) time, ensuring minimal length is found without checking all subarrays.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window is known for O(n) minimal subarray sum solutions [OK]

Hint: Minimal subarray sum -> variable-size sliding window [OK]

Common Mistakes:

• Thinking sorting helps with contiguous subarrays
• Assuming DP is needed for minimal length
• Using brute force for optimality

2. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

3. Consider the following Python code implementing the sliding window maximum using a monotonic deque. What is the returned result when calling maxSlidingWindow([2, 1, 3], 2)?

easy

A. [2, 3]

B. [2, 1, 3]

C. [3]

D. [1, 3]

Solution

1. Step 1: Trace the deque and result for each iteration

   i=0: dq=[0], result=[]; i=1: nums[1]=1 < nums[0]=2, dq=[0,1], result=[]; i=2: nums[2]=3 > nums[1]=1 pop 1, nums[2]=3 > nums[0]=2 pop 0, dq=[2]; after i=1 (window [2,1]) result append nums[0]=2; after i=2 (window [1,3]) result append nums[2]=3.

2. Step 2: Collect final result

   Result after full iteration is [2, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected sliding window maximum for windows [2,1] and [1,3] [OK]

Hint: Deque stores indices of max candidates, popping smaller elements [OK]

Common Mistakes:

• Appending result before window is full
• Not removing indices outside the window
• Confusing values and indices in deque

4. What is the time complexity of the optimal sliding window solution for the Grumpy Bookstore Owner problem when given an input array of length n and window size X?

medium

A. O(n)

B. O(n * X)

C. O(n + X)

D. O(n log n)

Solution

1. Step 1: Analyze outer loop

   The code iterates over the array once to compute base satisfaction (O(n)).

2. Step 2: Analyze sliding window loop

   The sliding window moves from start to end once, updating sums in O(1) per step, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant-time updates -> O(n) [OK]

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

Common Mistakes:

• Confusing with brute force O(n*X)
• Adding X to n instead of linear
• Assuming sorting needed

5. Suppose the bookstore owner can be calmed multiple times, each time for a continuous window of length X, possibly overlapping. How should the algorithm be modified to find the maximum total satisfied customers under this new condition?

hard

A. Sum all customers since calming multiple times removes grumpiness entirely

B. Run the original sliding window once and multiply the max extra by the number of windows allowed

C. Use a greedy approach to pick the top non-overlapping windows with highest extra satisfaction

D. Use dynamic programming to select multiple possibly overlapping windows maximizing total extra satisfaction

Solution

1. Step 1: Understand new problem constraints

   Multiple calming windows allowed, possibly overlapping, so simple sliding window max sum is insufficient.

2. Step 2: Identify suitable approach

   Dynamic programming can consider multiple windows and their overlaps to maximize total extra satisfaction.

3. Step 3: Why other options fail

   Multiplying max extra ignores overlaps; greedy picking non-overlapping windows misses overlaps; summing all customers ignores grumpy states.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DP handles multiple overlapping windows optimally [OK]

Hint: Multiple overlapping windows -> DP needed [OK]

Common Mistakes:

• Assuming single window solution suffices
• Ignoring overlaps in greedy
• Over-simplifying to sum all customers