DSA sheet · Arrays · Sliding Window pattern (fixed size)

Maximum Subarray with Sum K

This is the first question of the sliding window pattern in the sheet (on GFG it's called "Max Sum Subarray of size K"). The teacher uses it to introduce what a sliding window is. She first writes the natural two-loop brute force, works out the loop limits carefully, shows from the constraints why it gives TLE, rules out the other array patterns one by one, and then turns it into the fixed-size sliding window: "add the next number, subtract the leftmost".

Why it matters: this "add one, remove one" move is the heart of every fixed-size window problem (anagrams, sliding window maximum, permutation in string). Get this one perfectly and the rest are small changes.

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 · Sliding window from scratch
• Part A · Brute force: two loops over every window
• Part B · Optimal: fixed-size sliding window
• Part C · Revision page

Part 0 · Before starting

Subarray = window

A subarray is a piece of the array whose elements sit next to each other (contiguous): pick a start and an end, take everything between, skip nothing. In sliding-window language, a subarray is called a window, and we describe it as [left..right] (both ends included). Its length is right − left + 1.

The brute-force problem: repeated work

To look at every window we can use two loops: a start pointer, and an end pointer that walks forward and adds things up. There are about n²/2 windows (or n − k + 1 windows of a fixed size k, each costing k additions). Neighbouring windows share almost all their cells, but the brute force adds those shared cells again every time. Sliding window fixes exactly this.

Expand and shrink

• Expand: move right one step. A cell joins; add it to the running total.
• Shrink: move left one step. The oldest cell leaves; subtract it.

Both pointers only move forward, so in total they make at most 2n moves.

Fixed-size vs variable-size windows

Other shapes you'll meet later in this notebook: longest valid (record after shrinking), shortest valid (record while shrinking), count of valid windows (count += right − left + 1, because every start from left to right gives a valid window ending at right), and "exactly K = atMost(K) − atMost(K − 1)". Problem 1 (the overview) covers them all.

The 4 array patterns the teacher always checks

Part A · Brute force: two loops over every window

GFG "Max Sum Subarray of size K"

1The question in simple words

You get an array of integers arr and a number k. Look at every subarray of length exactly k, add up each one, and return the largest total.

The teacher's example, with k = 4:

All windows of size 4:

Can a window start at index 6 (value 1)? No: from there only 3 elements are left (1, 0, 20), not 4. So the last possible start is index 5.

2What the constraints tell us

• n up to 10⁶. Big. Anything like n·k can blow up (step 9).
• 1 ≤ arr[i] ≤ 10⁶ → all numbers are positive. No negatives. She asks us to remember this, because it rules out Kadane's later and tells us how to start the max.
• 1 ≤ k ≤ n → k can be as big as the whole array, so k can also reach 10⁶. And there's always at least one window.
• The biggest sum is 10⁶ × 10⁶ = 10¹². In Java/C++ that needs a long; Python ints never overflow.

3Intuition: list every window and add it up

The first thing that comes to mind: for every start position i, take the k numbers from i onwards, add them up, and keep the biggest total. Two loops: the outer one picks the start, the inner one adds k numbers.

4Building the loop limits from the example (the part she does slowly)

Where must the outer loop stop?

The indexes go 0 … 8, so n = 9. The last start that still has k = 4 numbers is index 5. And 5 = 9 − 4 = n − k. So the outer loop runs i from 0 up to and including n − k.

Where must the inner loop stop? (her j < k slip)

For every i we want exactly 4 numbers starting from i (not from i + 1). So j starts at i. She first tries j < k:

• i = 0: j = 0, 1, 2, 3 → 4 numbers ✓.
• i = 1: j = 1, 2, 3 → only 3 numbers ✗.
• i = 2: j = 2, 3 → only 2 ✗.

The fix: stop at i + k, not k. Then i = 0 gives 0..3, i = 1 gives 1..4, i = 2 gives 2..5. Always 4 numbers ✓.

Adding up and keeping the max

• Before the inner loop, set total = 0 (fresh for every start). Inside it, total += arr[j].
• After the inner loop, total is the sum of the window starting at i. Update best = max(best, total).

5Approach steps

1. best = 0, n = len(arr).
2. For each start i from 0 to n − k (inclusive): set total = 0.
3. For j from i to i + k − 1: total += arr[j].
4. best = max(best, total).
5. Return best.

6Code (Python)

class Solution:
    def maxSubarraySum(self, arr, k):
        n = len(arr)
        best = 0                         # safe: all numbers are positive
        for i in range(n - k + 1):       # last start is n - k (included)
            total = 0                    # fresh sum for this window
            for j in range(i, i + k):    # exactly k numbers from i
                total += arr[j]
            best = max(best, total)
        return best

7Code line by line

8Dry run (hand table)

arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4, n = 9 → i goes 0..5.

(On screen she first calls the third window 37, then corrects it to 38. 2 + 10 + 23 + 3 = 38.)

Answer: 39 ✓. Notice the work: windows 0 and 1 share 4, 2, 10, and we added those three numbers twice.

9Complexity & remember

• The outer loop runs n − k + 1 times and the inner loop k times, so time ≈ (n − k)·k = n·k − k², written O(n·k).
• Her TLE check: take n = 10⁶ and k = 10³ (allowed). n·k = 10⁹. k² = 10⁶, which is tiny next to 10⁹ ("100 crore minus a few lakh"), so it's still about 10⁹. Beyond about 10⁸ operations we get TLE. So this must be optimised.
• Space O(1).

Part B · Optimal: fixed-size sliding window

1The question again, with the new goal

Same question. The goal now is O(n): each element should be touched a constant number of times, not k times.

2What the constraints tell us now: choosing the pattern

Whenever she optimises an array problem, she goes through her four patterns and rules them out one by one:

• ✗ Two pointers: used when only the two numbers at two positions matter. Here every number inside the window matters (we add them all). So it's sliding window, prefix sum or Kadane's, but definitely not two pointers.
• ✗ Kadane's: she uses it when the array has negative numbers. The constraints say 1 ≤ arr[i], so no negatives → not Kadane's.
• ✗ Prefix sum: she uses it for many range queries ("sum from index 3 to 6, then 7 to 10…"). Here we just need normal sums of different consecutive subarrays.
• ✓ Sliding window: sums of different contiguous subarrays, all positive, one pass.

3Intuition: don't recount the middle

Look at the first two windows only, as if the array were just [1, 4, 2, 10, 23]:

The brute force runs the inner loop 4 times (indexes 0–3), then 4 more times (1–4). That's 8 additions for only 5 elements. The numbers 4, 2, 10 are added twice.

Window 2 is just window 1 with 23 added on the right and 1 removed from the left. So: compute the first window once; after that, every next window = previous sum + the new right number − the old left number. One add and one subtract is O(1), so the inner k-loop disappears. O(n·k) becomes O(n).

4Building the code from the example

Step 1: the first window

We can't slide until we have something to slide. So run a loop k times to get the first window's sum: window_sum = 1 + 4 + 2 + 10 = 17.

Step 2: where does the sliding loop start?

The first number to add is 23, at index 4. And 4 = k. So the second loop is j from k to n − 1.

Step 3: which index leaves? (her hint)

When j = 4 joins, index 0 must leave. How do we get 0 from j = 4? Subtract k: 4 − 4 = 0. Next, when j = 5 (value 3) joins, 5 − 4 = 1 leaves (value 4). It always works: the cell that leaves is j − k.

Step 4: how do we start best? (0 vs the first window)

She changes her mind here, on purpose. The sliding loop only compares the windows from the second one on. If best starts at 0, the first window is never compared. Her example: if the first window's sum were 50 (the biggest), starting at 0 would lose it. So start best with the first window's sum, "to be on the safe side".

5Approach steps

1. window_sum = 0. For i in 0..k−1: window_sum += arr[i]. (first window)
2. best = window_sum.
3. For j from k to n − 1: window_sum += arr[j] (new number joins), window_sum -= arr[j − k] (leftmost leaves).
4. best = max(best, window_sum).
5. Return best.

6Code (Python)

class Solution:
    def maxSubarraySum(self, arr, k):
        n = len(arr)
        window_sum = 0
        for i in range(k):               # first window: indexes 0..k-1
            window_sum += arr[i]
        best = window_sum                # the first window counts too
        for j in range(k, n):            # j = the number that joins
            window_sum += arr[j]         # add the new right number
            window_sum -= arr[j - k]     # remove the old left number
            best = max(best, window_sum)
        return best

7Code line by line

8Dry run (hand table)

arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4.

Answer: 39 ✓, the same as the brute force, with 4 + 5 = 9 steps instead of 6 × 4 = 24 additions.

9Complexity & remember

• The first loop runs k times. The second loop runs from k to n, so n − k times. Total: k + (n − k) = n. The k's cancel → time O(n).
• Space O(1): just a few variables.

Her Java submission was accepted, and this is the most optimised version.

Part C · Revision page

s = Solution()
print(s.maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4))   # 39
print(s.maxSubarraySum([100, 200, 300, 400], 2))             # 700
print(s.maxSubarraySum([50, 1, 1], 1))                       # 50 (first window is the max)
print(s.maxSubarraySum([1, 1, 9], 2))                        # 10 (last window is the max)
print(s.maxSubarraySum([5, 5, 5], 3))                        # 15 (k = n)

Based on this video: Maximum Sum Subarray of Size K | Sliding Window