DSA sheet · Arrays · Sliding Window pattern

Minimum Size Subarray Sum

The teacher calls this the start of the sliding window section after finishing two pointers. It's a medium problem, and it's the classic "shortest valid window" question. She first writes a brute force (two loops with an early break), explains why the answer must start at "infinity" and why we must return 0 when nothing works, then picks sliding window from her four array patterns. Her picture for sliding window is a leech: it stretches its front forward, then pulls its back in.

Why it matters: "shortest subarray that reaches a target" is the mirror image of "longest subarray that stays within a limit". The only real difference is where you record the answer, and this problem teaches that.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (sliding window from scratch)
• Part A · Brute force: every start, stop at the first valid end
• Part B · Optimal: expand until valid, shrink while still valid
• Part C · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array whose elements sit next to each other (contiguous). Choose a start index and an end index and take everything in between, with no skipping. (In strings this is called a substring.) Its length is end − start + 1.

The brute force over all windows, and why it repeats work

Two loops can check every subarray: one fixes the start, the other walks the end forward. There are n·(n+1)/2 subarrays, so this is O(n²). The waste: after checking [2, 3, 1, 2], the next start begins again with [3], re-adding 3, 1, 2 that we had already added. Sliding window keeps the running sum and only fixes the edges.

The window [left..right]: expand and shrink

A window is the current subarray, marked by two pointers: left (first index) and right (last index). We keep its sum in a variable so we never re-add it.

• Expand: move right forward, sum += nums[right].
• Shrink: sum -= nums[left], then move left forward.

The teacher's picture: a leech walking. It stretches its front end forward (that's right, the expansion), then pulls its back end up (that's left, the shrinking), and repeats. Both ends only ever move forward. When to expand and when to shrink depends on the question.

Fixed-size vs variable-size windows

Longest vs shortest vs count

Another trick you'll meet later: "exactly K" = atMost(K) − atMost(K − 1). Not needed here.

Why sliding window needs positive numbers

Shrinking only makes sense if the rule is monotonic: adding an element must always push the sum up, and removing one must always push it down. With all numbers positive (here every nums[i] ≥ 1), that's guaranteed. If negatives were allowed, adding could lower the sum and removing could raise it, so the window could stop too early and miss answers. (That's why "Subarray Sum Equals K", which allows negatives, uses prefix sums instead.)

Other tools in this pattern (not needed here)

• Frequency map (dict / collections.Counter): value → how many times it's in the window, for rules about distinct values.
• Monotonic deque: keeps indexes in decreasing order of value, used only for Sliding Window Maximum.

The teacher's 4 array patterns

Part A · Brute force: every start, stop at the first valid end

LeetCode 209

1The question in simple words

You get an array of positive integers nums and a positive integer target. Among all subarrays whose sum is greater than or equal to target, return the smallest length. If no subarray reaches target, return 0.

Many subarrays reach 7 ([2,3,1,2] = 8, [3,1,2,4] = 10, [1,2,4] = 7, …). We don't want all of them, only the length of the shortest one.

2What the constraints tell us

• 1 ≤ target ≤ 10⁹. An int holds up to about 2.1·10⁹ (INT_MAX), so it fits. (Python ints never overflow anyway.)
• 1 ≤ n ≤ 10⁵. O(n) is 10⁵ steps. O(n²) is 10¹⁰, far past the ~10⁸ limit, so an O(n²) solution will not pass. We must optimise, but she shows the brute force first.
• 1 ≤ nums[i] ≤ 10⁴. All numbers are positive (they start at 1). No negatives → sums only grow as a subarray gets longer. This is what allows both the early break and the sliding window. (She reads the limit as 10⁵ once and 10⁴ later; LeetCode says 10⁴. The largest possible sum, 10⁵ × 10⁴ = 10⁹, is still safe.)

3Intuition: try every start, extend until it's enough

Fix a starting index i. Move a second pointer j from i forward, adding each number to a running sum. As soon as the sum reaches target, we have the shortest valid subarray that starts at i. Record its length and move on to the next start.

4Building the logic from the example

Start at index 0 (value 2), target 7

Why break as soon as it's valid

[2,3,1,2,4] also has sum ≥ 7, and so does [2,3,1,2,4,3]. They're valid, but they're longer, and we want the minimum length. Going further from the same start can only give longer subarrays, so the extra work is useless → break.

The length: j − i + 1

Think of i as the left pointer and j as the right pointer. The number of elements from i to j is j − i + 1. Here 3 − 0 + 1 = 4.

Keeping the minimum, and why it starts at "infinity"

We keep an answer variable and update it with ans = min(ans, length). What should ans start as?

• If it started at 0, then min(0, 4) = 0, min(0, 3) = 0… it would stay 0 forever. Wrong.
• So it must start at a huge value that any real length beats. In Java that's Integer.MAX_VALUE. In Python we use float('inf').

The other starts

• Start 1 (3): 3, 4, 6, 10 → valid at length 4. min(4, 4) = 4, no change. Break.
• Start 2 (1): 1, 3, 7 → 7 ≥ 7 (equal counts!) → length 3. ans = 3. Break.
• Start 3 (2): 2, 6, 9 → length 3. Still 3. Break.
• Start 4 (4): 4, 7 → length 2. ans = 2. Break.
• Start 5 (3): 3, end of array. Never valid.

The case she almost forgot: no valid subarray → 0

Halfway through, the teacher realises something is missing. Suppose the whole array adds up to only 15 (2+3+1+2+4+3) but target is 20. No subarray can reach it, so ans is never updated and is still infinity. We can't return infinity. The question says to return 0 in that case.

5Approach steps

1. ans = infinity.
2. For each start i: total = 0 (fresh sum for this start).
3. For j from i to n − 1: add nums[j].
4. If total ≥ target: ans = min(ans, j − i + 1) and break.
5. After both loops: return 0 if ans is still infinity, else ans.

6Code (Python)

class Solution:
    def minSubArrayLen(self, target, nums):
        n = len(nums)
        ans = float('inf')                  # "nothing found yet"
        for i in range(n):                  # start of the subarray
            total = 0                       # fresh sum for this start
            for j in range(i, n):           # end of the subarray
                total += nums[j]
                if total >= target:         # first valid end for this start
                    ans = min(ans, j - i + 1)
                    break                   # longer ones can't be better
        return 0 if ans == float('inf') else ans

7Code line by line

8Dry run (hand table)

nums = [2, 3, 1, 2, 4, 3], target = 7.

Final answer: 2 ✓ ([4, 3]).

9Complexity & remember

• Time O(n²): i visits each index once, and for each i, j can run nearly to the end (n, then n − 1, then n − 2 …). With n = 10⁵ that's about 10¹⁰ in the worst case → TLE. The teacher says submitting it would time out because it's far too slow.
• Space O(1).

Part B · Optimal: expand until valid, shrink while still valid

LeetCode 209

1The question again, with the new goal

Same question. The goal now is O(n): one pass where left never goes back to restart.

2Choosing the pattern

• Two pointers ✗: it works with two particular points and only those two. Here the sum needs every number between the two points.
• Sliding window ✓: two points and everything in between. The subarray sum from i to j needs every number between them.
• Prefix sum ✗: it shines when we're asked many range-sum queries ("sum from this index to that index?"). We aren't, so it isn't needed.
• Kadane's ✗: for maximum sums with negative numbers. The constraints say numbers start at 1, so there are no negatives.

3Intuition: the leech

left and right start at 0, and the window sum starts at 0.

• Expand (stretch the front): keep moving right and adding, as long as the sum is still below target. A short window that isn't enough yet is no use.
• The moment the sum is ≥ target, we have a valid window. Record its length. But maybe it's longer than it needs to be.
• Shrink (pull the back in): moving right further would only make it longer, so to get shorter we must move left. Remove from the left and record again, as long as it stays valid.
• Once it drops below target, go back to expanding.

4Building the logic from examples

First, the expansion on [2, 3, 1, 2, 4, 3], target 7

right = 0: sum 2, not enough. right = 1: sum 5. right = 2: sum 6. Still below 7, so nothing to record and no reason to shrink. Just keep moving right (the for loop does this for us).

right = 3: sum 8 ≥ 7. Valid! Length right − left + 1 = 3 − 0 + 1 = 4. We don't know yet if it's the minimum, but it's a valid length, so ans = min(ans, 4) = 4.

Then the shrink: subtract the left value, move left

To make the window shorter we take out the left element: total -= nums[left], then left += 1. Removing 2: sum 8 → 6. Now 6 < 7, the window [3, 1, 2] is no longer valid, so we stop shrinking and go back to expanding.

Why while, not if: her [1, 1, 1, 5] example

The teacher asks: should the shrink happen once (if) or repeatedly (while)? Take nums = [1, 1, 1, 5], target = 6.

With an if, we'd shrink once and report 3. The correct answer is 2. So we keep shrinking until the condition becomes false. The last length recorded before it broke is the shortest valid window for this right end.

Where exactly to record the answer

Inside the while, we record the length before removing the left element. At that moment the window is guaranteed valid (that's what the while condition just checked). After the loop ends, the window is invalid, so recording there would be wrong. This is the opposite of "longest window" problems, where you record after shrinking.

Continuing her dry run

• right = 4 (value 4): sum 6 + 4 = 10 ≥ 7. Window [3, 1, 2, 4], length 4, not better than 4. Shrink: remove 3 → sum 7, still valid → window [1, 2, 4], length 3 → ans 3. Remove 1 → sum 6, invalid → stop.
• right = 5 (value 3): sum 9 ≥ 7. Window [2, 4, 3], length 3, no change. Shrink: remove 2 → sum 7, valid → window [4, 3], length 2 → ans 2. Remove 4 → sum 3, invalid → stop.
• right reaches the end. Answer 2 ✓.

5Approach steps

1. left = 0, total = 0, ans = infinity.
2. For each right: total += nums[right] (expand).
3. While total ≥ target: record ans = min(ans, right − left + 1), then total -= nums[left] and left += 1 (shrink).
4. After the loop: return 0 if ans is still infinity, else ans.

6Code (Python)

class Solution:
    def minSubArrayLen(self, target, nums):
        total = 0                            # sum of the current window
        left = 0
        min_len = float('inf')               # "nothing found yet"
        for right in range(len(nums)):
            total += nums[right]             # expand: stretch the front
            while total >= target:           # valid: try to make it shorter
                min_len = min(min_len, right - left + 1)   # record first
                total -= nums[left]          # then pull the back in
                left += 1
        return 0 if min_len == float('inf') else min_len

7Code line by line

8Dry run

nums = [2, 3, 1, 2, 4, 3], target = 7. In the shrink column, each line is one pass of the while loop.

The array at the key moments (yellow = window, grey = left behind):

Final answer: 2 ✓, the same as the brute force.

9Complexity & remember

• Time O(n): right touches each index once. left also touches each index at most once, because it never goes back and restarts for a new right. The while inside the for looks nested, but the total moves are n + n = 2n → O(n).
• Space O(1): three variables.

She submitted it and it beat about 99.7%, as expected for a linear solution.

Part C · Revision page

s = Solution()
print(s.minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))     # 2
print(s.minSubArrayLen(6, [1, 1, 1, 5]))           # 2  (needs while, not if)
print(s.minSubArrayLen(4, [1, 4, 4]))              # 1
print(s.minSubArrayLen(11, [1, 1, 1, 1, 1, 1]))    # 0  (no valid window)
print(s.minSubArrayLen(20, [2, 3, 1, 2, 4, 3]))    # 0  (total is only 15)
print(s.minSubArrayLen(15, [2, 3, 1, 2, 4, 3]))    # 6  (the whole array)

Based on this video: Minimum Size Subarray Sum | Sliding Window