Maximum Sum Subarray of Size K

▶

Steps

setup

Initialize window sum with first K elements

Calculate the sum of the first 3 elements to initialize the sliding window sum and set it as the current maximum sum.

💡 Starting with the first window sum gives a baseline to compare all subsequent windows against.

Line:

window_sum = sum(arr[:k])
max_sum = window_sum

💡 The initial window sum is the first candidate for the maximum sum subarray.

expand

Slide window right by 1: remove leftmost, add next element

Move the window one step to the right by subtracting the element leaving the window (2) and adding the new element entering (1).

💡 Updating the sum by subtracting and adding elements avoids recomputing the entire sum.

Line:

window_sum += arr[i] - arr[i - k]

💡 The window sum is efficiently updated to reflect the new window contents.

compare

Compare updated window sum to max sum

Check if the new window sum (7) is greater than the current max sum (8). It is not, so max sum remains unchanged.

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

Line:

if window_sum > max_sum:
    max_sum = window_sum

💡 Not every window sum update changes the maximum sum; some windows have smaller sums.

expand

Slide window right by 1: update sum for next window

Move the window right by removing the element at index 1 (1) and adding the element at index 4 (3).

💡 Sliding the window keeps the size fixed while updating the sum efficiently.

Line:

window_sum += arr[i] - arr[i - k]

💡 The window now covers indices 2 to 4 with a new sum.

compare

Compare updated window sum to max sum

Check if the new window sum (9) is greater than the current max sum (8). It is, so update max sum to 9.

💡 Updating max sum tracks the best subarray found so far.

Line:

if window_sum > max_sum:
    max_sum = window_sum

💡 The subarray [5, 1, 3] is currently the best candidate.

expand

Slide window right by 1: update sum for next window

Move the window right by removing the element at index 2 (5) and adding the element at index 5 (2).

💡 Continuing to slide the window to check all possible subarrays of size K.

Line:

window_sum += arr[i] - arr[i - k]

💡 The window now covers indices 3 to 5 with a new sum.

compare

Compare updated window sum to max sum

Check if the new window sum (6) is greater than the current max sum (9). It is not, so max sum remains 9.

💡 Only update max sum if the current window sum is higher.

Line:

if window_sum > max_sum:
    max_sum = window_sum

💡 The last window sum is smaller than the max sum found earlier.

reconstruct

End of array reached, return max sum

All windows of size K have been evaluated. The maximum sum found is 9.

💡 The algorithm terminates with the best sum found during the sliding process.

Line:

return max_sum

💡 The maximum sum subarray of size K is identified as 9.

reconstruct

Highlight final answer window

The subarray [5, 1, 3] from indices 2 to 4 is the maximum sum subarray of size 3 with sum 9.

💡 Showing the final window helps visualize the solution subarray.

💡 The maximum sum subarray is clearly identified by its indices and sum.

reconstruct

Final state with answer summary

The algorithm returns the maximum sum 9 and the window indices (2 to 4) representing the subarray.

💡 Summarizing the result confirms the algorithm's output and window position.

💡 The final answer and window are clearly presented for review.

def max_sum_subarray_k1_optimized(arr, k):
    # STEP 1: Initialize window sum and max sum
    if k == 1:
        return max(arr)
    window_sum = sum(arr[:k])  # STEP 1
    max_sum = window_sum       # STEP 1
    for i in range(k, len(arr)):
        # STEP 2,4,6: Slide window right by 1
        window_sum += arr[i] - arr[i - k]  # STEP 2,4,6
        # STEP 3,5,7: Compare and update max sum
        if window_sum > max_sum:  # STEP 3,5,7
            max_sum = window_sum  # STEP 3,5,7
    # STEP 8: Return max sum
    return max_sum  # STEP 8

# Driver code
if __name__ == '__main__':
    arr = [2, 1, 5, 1, 3, 2]
    k = 3
    print(max_sum_subarray_k1_optimized(arr, k))  # Output: 9

📊

Maximum Sum Subarray of Size K - Watch the Algorithm Execute, Step by Step

Watching the window expand and slide while tracking sums helps you understand how to optimize subarray sum calculations without recomputing sums from scratch.

expand

L ▼

2

0

1

1

R ▼

5

2

1

3

3

4

2

5

Window: [2, 1, 5]

Metric: 8

Answer: 8

expand

2

0

L ▼

1

1

5

2

R ▼

1

3

3

4

2

5

Window: [1, 5, 1]

Metric: 7

Answer: 8

record_answer

2

0

L ▼

1

1

5

2

R ▼

1

3

3

4

2

5

Window: [1, 5, 1]

Metric: 7

Answer: 8

expand

2

0

1

1

L ▼

5

2

1

3

R ▼

3

4

2

5

Window: [5, 1, 3]

Metric: 9

Answer: 8

record_answer

2

0

1

1

L ▼

5

2

1

3

R ▼

3

4

2

5

Window: [5, 1, 3]

Metric: 9

Answer: 9

expand

2

0

1

1

5

2

L ▼

1

3

3

4

R ▼

2

5

Window: [1, 3, 2]

Metric: 6

Answer: 9

record_answer

2

0

1

1

5

2

L ▼

1

3

3

4

R ▼

2

5

Window: [1, 3, 2]

Metric: 6

Answer: 9

record_answer

2

0

1

1

L ▼

5

2

1

3

R ▼

3

4

2

5

Window: [5, 1, 3]

Metric: 9

Answer: 9

record_answer

2

0

1

1

L ▼

5

2

1

3

R ▼

3

4

2

5

Window: [5, 1, 3]

Metric: 9

Answer: 9

record_answer

2

0

1

1

L ▼

5

2

1

3

R ▼

3

4

2

5

Window: [5, 1, 3]

Metric: 9

Answer: 9

Key Takeaways

✓ Sliding window updates the sum efficiently by adding the new element and subtracting the old one.

This avoids recomputing the sum from scratch for each window, which is a key optimization.

✓ The maximum sum is updated only when a strictly larger window sum is found.

This ensures the algorithm tracks the best subarray without unnecessary updates.

✓ The fixed window size means the window always shrinks from the left as it expands to the right.

Understanding this movement clarifies how the window slides across the array.

Practice

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

2. You have a row of cards with points on each card. You can pick exactly k cards from either the start or the end of the row to maximize your total points. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a greedy algorithm that always picks the card with the highest immediate point value from either end.

B. Use a sliding window to find the minimum sum subarray of length n - k and subtract it from the total sum of all cards.

C. Use dynamic programming to consider all combinations of picking cards from the middle of the array.

D. Use a brute force approach that tries all possible combinations of picking k cards from anywhere in the array.

Solution

1. Step 1: Understand the problem constraints

   The problem restricts picking cards only from the start or end, so the chosen cards form a prefix and suffix combination.

2. Step 2: Recognize the sliding window pattern

   Picking k cards from ends is equivalent to removing a contiguous subarray of length n-k from the middle. Finding the minimum sum subarray of length n-k lets us maximize the points from the ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window on middle subarray -> optimal and efficient [OK]

Hint: Sliding window on middle subarray finds minimal removal [OK]

Common Mistakes:

• Greedy picking highest immediate card fails on future gains
• Brute force is too slow for large inputs
• DP on middle cards is unnecessary and inefficient

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. Consider the following buggy code for maxSatisfied. Which line contains the subtle bug that causes incorrect results on some inputs?

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] == 0:
            window_sum -= customers[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

medium

A. Line checking if grumpy[i] == 1 before adding customers[i]

B. Line initializing base_satisfied with customers where grumpy[i] == 0

C. Line checking if grumpy[i - X] == 0 before subtracting customers[i - X]

D. Line updating max_extra when window_sum > max_extra

Solution

1. Step 1: Identify subtraction condition

   The code subtracts customers[i - X] only if grumpy[i - X] == 0, but it should subtract only if grumpy[i - X] == 1 because only grumpy customers were added.

2. Step 2: Consequence of bug

   This causes incorrect window sums, as some grumpy customers are never subtracted, inflating window_sum.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Subtraction condition must match addition condition [OK]

Hint: Check symmetry of add and subtract conditions [OK]

Common Mistakes:

• Confusing grumpy check in subtraction
• Forgetting to subtract outgoing element
• Mixing base satisfaction with window sums

5. What is the time complexity of the sliding window solution for finding the maximum average subarray of size k in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each element is added and removed exactly once from the window sum

B. O(n*k) because each window sum is recomputed from scratch

C. O(n log k) due to sorting elements within each window

D. O(k) because the window size dominates the computation

Solution

1. Step 1: Analyze loop operations

   The sliding window sums are updated by adding one new element and removing one old element per iteration, so each element is processed twice.

2. Step 2: Identify complexity

   Since the loop runs n-k times and each iteration is O(1), total time is O(n). The common mistake is thinking sum is recomputed fully each time, which is O(n*k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in constant time per iteration [OK]

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

Common Mistakes:

• Assuming sum recomputed fully each window
• Confusing window size k with input size n