Minimum Size Subarray Sum

▶

Steps

setup

Initialize pointers and variables

Set left and right pointers to 0, current_sum to 0, and min_length to infinity before starting the iteration.

💡 Initialization sets the stage for the sliding window to start empty and min_length to a large value so any valid subarray will update it.

Line:

n = len(nums)
left = 0
current_sum = 0
min_length = float('inf')

💡 The algorithm starts with an empty window and no sum accumulated.

expand

Expand window: include nums[0] = 2

Move right pointer from -1 to 0 and add nums[0] (2) to current_sum, making current_sum = 2.

💡 Expanding the window adds elements to the sum, trying to reach the target sum.

Line:

for right in range(n):
    current_sum += nums[right]

💡 The window now covers [2] with sum 2, still less than target 7.

expand

Expand window: include nums[1] = 3

Move right pointer to 1 and add nums[1] (3) to current_sum, updating current_sum to 5.

💡 Continuing to expand the window to accumulate sum towards the target.

Line:

for right in range(n):
    current_sum += nums[right]

💡 Window covers [2,3] with sum 5, still less than target 7.

expand

Expand window: include nums[2] = 1

Move right pointer to 2 and add nums[2] (1) to current_sum, updating current_sum to 6.

💡 Adding more elements to try to reach or exceed the target sum.

Line:

for right in range(n):
    current_sum += nums[right]

💡 Window covers [2,3,1] with sum 6, still less than target 7.

expand

Expand window: include nums[3] = 2

Move right pointer to 3 and add nums[3] (2) to current_sum, updating current_sum to 8.

💡 Sum now exceeds target, triggering the inner loop to try shrinking the window.

Line:

for right in range(n):
    current_sum += nums[right]

💡 Window covers [2,3,1,2] with sum 8, which is >= target 7.

shrink

Shrink window: update min_length and move left

Since current_sum (8) >= target, update min_length to 4 (window size), subtract nums[left] (2) from current_sum, and move left to 1.

💡 Shrinking the window tries to find a smaller valid subarray while maintaining sum >= target.

Line:

while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

💡 We found a valid subarray of length 4 and try to shrink it further.

expand

Expand window: include nums[4] = 4

Move right pointer to 4 and add nums[4] (4) to current_sum, updating current_sum to 10.

💡 Expanding again to reach or exceed the target sum after shrinking.

Line:

for right in range(n):
    current_sum += nums[right]

💡 Window covers [3,1,2,4] with sum 10, which is >= target 7.

shrink

Shrink window: update min_length and move left

Since current_sum (10) >= target, update min_length to 4 (window size), subtract nums[left] (3) from current_sum, and move left to 2.

💡 Try to shrink the window to find a smaller valid subarray.

Line:

while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

💡 Window shrinks to [1,2,4] with sum 7, still valid.

shrink

Shrink window: update min_length and move left again

Still current_sum (7) >= target, update min_length to 3 (window size), subtract nums[left] (1) from current_sum, and move left to 3.

💡 Keep shrinking to find the smallest valid window.

Line:

while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

💡 Window shrinks to [2,4] with sum 6, which is less than target, so stop shrinking.

expand

Expand window: include nums[5] = 3

Move right pointer to 5 and add nums[5] (3) to current_sum, updating current_sum to 9.

💡 Expand window again to reach or exceed target after shrinking.

Line:

for right in range(n):
    current_sum += nums[right]

💡 Window covers [2,4,3] with sum 9, which is >= target 7.

shrink

Shrink window: update min_length and move left

Since current_sum (9) >= target, update min_length to 3 (window size), subtract nums[left] (2) from current_sum, and move left to 4.

💡 Try to shrink the window to find a smaller valid subarray.

Line:

while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

💡 Window shrinks to [4,3] with sum 7, still valid.

shrink

Shrink window: update min_length and move left again

Still current_sum (7) >= target, update min_length to 2 (window size), subtract nums[left] (4) from current_sum, and move left to 5.

💡 Keep shrinking to find the smallest valid window.

Line:

while current_sum >= target:
    min_length = min(min_length, right - left + 1)
    current_sum -= nums[left]
    left += 1

💡 Window shrinks to [3] with sum 3, which is less than target, so stop shrinking.

reconstruct

End of array reached, return answer

Right pointer has reached the end of the array. Return min_length 2 as the shortest subarray length with sum >= target.

💡 The algorithm finishes by returning the smallest window size found.

Line:

return 0 if min_length == float('inf') else min_length

💡 The minimal length subarray is of length 2, corresponding to [4,3].

def min_subarray_len(target, nums):
    n = len(nums)  # STEP 1
    left = 0      # STEP 1
    current_sum = 0  # STEP 1
    min_length = float('inf')  # STEP 1
    for right in range(n):  # STEP 2-12
        current_sum += nums[right]  # STEP 2,3,4,5,7,10
        while current_sum >= target:  # STEP 6,8,9,11,12
            min_length = min(min_length, right - left + 1)  # STEP 6,8,9,11,12
            current_sum -= nums[left]  # STEP 6,8,9,11,12
            left += 1  # STEP 6,8,9,11,12
    return 0 if min_length == float('inf') else min_length  # STEP 13

if __name__ == '__main__':
    print(min_subarray_len(7, [2,3,1,2,4,3]))  # Output: 2

📊

Minimum Size Subarray Sum - Watch the Algorithm Execute, Step by Step

Watching the window boundaries move and the sum change in real time reveals how the algorithm efficiently narrows down the minimal subarray length without checking all subarrays.

expand

L ▼

2

0

3

1

1

2

2

3

4

4

3

5

Metric: 0

Answer: ∞

expand

L=R

2

0

3

1

1

2

2

3

4

4

3

5

Window: [2]

Metric: 2

Answer: ∞

expand

L ▼

2

0

R ▼

3

1

1

2

2

3

4

4

3

5

Window: [2, 3]

Metric: 5

Answer: ∞

expand

L ▼

2

0

3

1

R ▼

1

2

2

3

4

4

3

5

Window: [2, 3, 1]

Metric: 6

Answer: ∞

expand

L ▼

2

0

3

1

1

2

R ▼

2

3

4

4

3

5

Window: [2, 3, 1, 2]

Metric: 8

Answer: ∞

shrink

2

0

L ▼

3

1

1

2

R ▼

2

3

4

4

3

5

Window: [3, 1, 2]

Metric: 6

Answer: 4

expand

2

0

L ▼

3

1

1

2

2

3

R ▼

4

4

3

5

Window: [3, 1, 2, 4]

Metric: 10

Answer: 4

shrink

2

0

3

1

L ▼

1

2

2

3

R ▼

4

4

3

5

Window: [1, 2, 4]

Metric: 7

Answer: 4

shrink

2

0

3

1

1

2

L ▼

2

3

R ▼

4

4

3

5

Window: [2, 4]

Metric: 6

Answer: 3

expand

2

0

3

1

1

2

L ▼

2

3

4

4

R ▼

3

5

Window: [2, 4, 3]

Metric: 9

Answer: 3

shrink

2

0

3

1

1

2

2

3

L ▼

4

4

R ▼

3

5

Window: [4, 3]

Metric: 7

Answer: 3

shrink

2

0

3

1

1

2

2

3

4

4

L=R

3

5

Window: [3]

Metric: 3

Answer: 2

record_answer

2

0

3

1

1

2

2

3

L ▼

4

4

R ▼

3

5

Window: [4, 3]

Metric: 7

Answer: 2

Key Takeaways

✓ The sliding window expands to accumulate sum until it meets or exceeds the target, then shrinks to find the minimal length subarray.

This dynamic adjustment is hard to grasp from code alone but becomes clear when watching the window boundaries move and sum update.

✓ The algorithm never re-examines subarrays that cannot improve the answer, making it efficient with O(n) time complexity.

Seeing the window only move forward and shrink without backtracking clarifies why this approach is optimal.

✓ Each time the sum condition is met, the algorithm updates the answer and tries to shrink the window, demonstrating the greedy approach to minimize length.

The decision to shrink immediately after reaching the target sum is a key insight that is subtle in code but obvious in visualization.

Practice

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

2. The following code attempts to solve the Max Consecutive Ones III problem. Identify the line that contains a subtle bug causing incorrect results on some inputs.

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)
        max_length = max(max_length, right - left + 1)
        if len(zero_positions) > k:
            left = zero_positions.popleft() + 1
    return max_length

medium

A. Line returning max_length at the end

B. Line appending zero index to zero_positions

C. Line updating max_length before shrinking the window

D. Line initializing left pointer to 0

Solution

1. Step 1: Understand window shrinking condition

   The window must shrink before updating max_length to ensure the window contains at most k zeros.

2. Step 2: Identify bug in max_length update timing

   Updating max_length before shrinking allows counting invalid windows with more than k zeros, causing incorrect max_length.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after window is valid [OK]

Common Mistakes:

• Updating max_length before shrinking window
• Not shrinking window at all
• Incorrect zero count tracking

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

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