Maximum Sum Subarray of Size K (Fixed-Size Sliding Window)

• Fixed-size sliding window – a window of exactly k consecutive elements slides across the array one position at a time.
• Sum update – instead of recomputing from scratch, add the incoming element and subtract the outgoing element in O(1).
• Maximum tracking – compare the updated sum against the best seen so far after each slide.
• Complexity – O(n) time, O(1) extra space.
• Precondition – k must not exceed the array length; if it does, no valid window exists.

What is the problem?

Given an array of positive numbers and a window size k, find the maximum sum of any contiguous subarray of exactly k elements. For example, for [2, 1, 5, 1, 3, 2] with k = 3, the maximum window sum is 5 + 1 + 3 = 9.

At the National Bank of India, the analytics team reviews daily deposit amounts and wants to highlight the best stretch of exactly k consecutive days.

Why does the brute-force approach fail?

The brute-force computes the sum of every window independently, which repeats most of the additions.

// Brute force: O(n * k)
int maxSum = 0;
for (int i = 0; i <= n - k; i++) {
    int windowSum = 0;
    for (int j = i; j < i + k; j++) {
        windowSum += deposits[j];
    }
    maxSum = Math.max(maxSum, windowSum);
}

Consecutive windows overlap in k-1 elements. Recomputing those shared elements is wasted work.

How does the sliding window work?

Compute the sum of the first k elements once. Then slide: add the element entering on the right and subtract the element leaving on the left.

package com.bank.analytics;

public class MaxSumWindowK {
    public static int maxSumSubarray(int[] deposits, int k) {
        if (k > deposits.length) {
            throw new IllegalArgumentException("k exceeds array length");
        }

        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += deposits[i];
        }
        int maxSum = windowSum;

        for (int i = k; i < deposits.length; i++) {
            windowSum += deposits[i] - deposits[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] deposits = {3000, 1000, 4000, 1000, 5000, 2000};
        int k = 3;
        System.out.println("Best " + k + "-day deposit total: " + maxSumSubarray(deposits, k));
    }
}

Best 3-day deposit total: 10000

What happens at each slide step?

For deposits [3000, 1000, 4000, 1000, 5000, 2000] with k = 3:

• Window [3000, 1000, 4000] sum = 8000. Max = 8000.
• Slide: add 1000, subtract 3000. Window [1000, 4000, 1000] sum = 6000. Max = 8000.
• Slide: add 5000, subtract 1000. Window [4000, 1000, 5000] sum = 10000. Max = 10000.
• Slide: add 2000, subtract 4000. Window [1000, 5000, 2000] sum = 8000. Max = 10000.

Answer: 10000.

What is the time and space complexity?

| Approach | Time | Space |
|---|---|---|
| Fixed-size sliding window | O(n) | O(1) |
| Brute force | O(n * k) | O(1) |

The sliding window visits each element exactly once and uses only a running sum and a max variable.

How is this different from a variable-size sliding window?

| Fixed-Size Window | Variable-Size Window |
|---|---|
| Window size is constant (k) | Window grows and shrinks |
| Add-one, subtract-one per slide | Expand right, shrink left on condition |
| Example: max sum of size k | Example: smallest subarray with sum >= target |
| Simple: no shrink condition | Complex: condition-based shrink loop |

What are the edge cases?

• k equals array length: the entire array is the only window; return its sum.
• k equals 1: return the maximum single element.
• k exceeds array length: no valid window; throw an exception or return a sentinel.
• All elements equal: every window has the same sum.

int[] a = {5, 5, 5, 5};
// k = 2: every window sums to 10
// k = 4: only window sums to 20
// k = 5: invalid, no window exists

What are common mistakes?

Forgetting to handle the case where k exceeds the array length is the most common mistake.

// Wrong: no check, causes ArrayIndexOutOfBoundsException
public static int maxSum(int[] arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i]; // crashes if k > arr.length
    // ...
}

// Correct: validate first
if (k > arr.length) throw new IllegalArgumentException("k exceeds array length");

What should a senior engineer know?

The fixed-size sliding window is one of the simplest and most useful array techniques. It applies to any problem that asks about a contiguous block of fixed size: maximum sum, maximum average, minimum sum, or any aggregate.

For streaming data where elements arrive one at a time, the same technique works by maintaining a circular buffer of size k. When a new element arrives, evict the oldest and update the running aggregate.

What are common interview follow-up questions?

• Find the maximum average of any subarray of size k. (Divide the max sum by k.)
• Find the first negative in every window of size k. (Use a deque.)
• Find the maximum of every window of size k. (Use a monotonic deque for O(n) time.)