Sliding Window (Max Sum)

Intuition

Say a shop wants its best three-day sales streak from a month of daily totals. The slow way is to add days 1 to 3, then days 2 to 4 from scratch, then days 3 to 5, and so on. But look at what changes between two neighbouring windows: one day falls off the front and one new day joins the back. Everything in the middle is identical. So keep a running total, subtract the day that leaves, add the day that arrives, and you get the next window's sum with two operations no matter how wide the window is.

It is like looking out of a train window: the frame stays the same width, and as the train moves, one telegraph pole slides out of view on one side while another slides in on the other. You do not need to recount every pole in the frame each second.

How it works step by step

1. Check that 1 <= k <= n; otherwise there is no valid window.
2. Sum the first k elements to get window, and set best = window.
3. For each index i from k to n - 1: add nums[i] (the element entering on the right) and subtract nums[i - k] (the element leaving on the left).
4. Update best = max(best, window).
5. Return best. If you also need the position, record the start index i - k + 1 whenever best improves.

Dry run

Input [2, 1, 5, 1, 3, 2], window size k = 3.

The answer is 9, from the window [5, 1, 3]. Every step did one addition and one subtraction, even though each window holds three numbers. With k = 1,000 the saving is a factor of about 500.

Code

public class MaxSumWindow {
    /** Maximum sum of any k consecutive elements. Requires 1 <= k <= nums.length. */
    public static long maxSum(int[] nums, int k) {
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("k must be between 1 and nums.length");
        }
        long window = 0;
        for (int i = 0; i < k; i++) window += nums[i];
        long best = window;
        for (int i = k; i < nums.length; i++) {
            window += (long) nums[i] - nums[i - k]; // one in, one out
            best = Math.max(best, window);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxSum(new int[] {2, 1, 5, 1, 3, 2}, 3)); // 9
        System.out.println(maxSum(new int[] {-4, -2, -7}, 2));      // -6
    }
}

def max_sum_window(nums, k):
    """Maximum sum of any k consecutive elements (1 <= k <= len(nums))."""
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best


print(max_sum_window([2, 1, 5, 1, 3, 2], 3))  # 9
print(max_sum_window([-4, -2, -7], 2))        # -6

The Java version accumulates in a long and casts before subtracting, so even values near the int limit cannot overflow. Python integers are unbounded, so no care is needed there.

Time and space complexity

The initial window costs k additions and each of the remaining n - k slides costs two operations, so the total is O(n) regardless of k. Only the running sum and the best value are stored. Prefix sums also give O(n), but they spend an extra array; their advantage is answering many different range queries later.

Edge cases

• k == n: there is exactly one window and the loop body never runs.
• k == 1: the answer is simply the maximum element.
• k > n or k <= 0: no valid window; throw, or return whatever the problem specifies.
• All negative numbers: initialise best from the first window, never from 0, or you will report a sum that no window has.
• Very large values or long arrays: use a 64-bit accumulator.
• Empty input: covered by the k > n check since any valid k is at least 1.

Common mistakes

• Initialising `best = 0`. With all-negative input the true answer is negative, and 0 is wrong.
• Off-by-one on the leaving element. When nums[i] enters, the element leaving is nums[i - k], not nums[i - k + 1] or nums[i - 1].
• Forgetting to compare the first window. If you only update best inside the loop, the case k == n returns nothing meaningful.
• Using a fixed window for a variable-size problem. 'Longest substring with at most k distinct characters' needs a window that grows and shrinks, driven by a condition, not a fixed width.
• Confusing max sum with max element. 'Sliding window maximum' (the largest single value in each window) needs a monotonic deque, not a running sum.

Variations and when to use it

Fixed-size windows (this lesson) handle maximum or average of k consecutive elements, counting windows that satisfy a threshold, and the count of vowels in every length-k substring. Variable-size windows expand the right edge every step and shrink the left edge while the window violates a rule, which solves longest substring without repeats, minimum size subarray sum, and the 'flip at most k zeroes' family. Both are special cases of two pointers moving in the same direction.

Use a sliding window when the problem talks about a contiguous subarray or substring and the quantity you track can be updated incrementally as one element enters and one leaves (sums, counts, frequency maps). If elements are not contiguous, or the aggregate cannot be undone when an element leaves (like a maximum without a deque), you need a different tool. For the max sum of any length, not a fixed k, the right algorithm is Kadane's, not a window.

Related LeetCode problems

• #643 Maximum Average Subarray I — the max-sum window divided by k at the end.
• #1456 Maximum Number of Vowels in a Substring of Given Length — the same slide, but the running value is a vowel count.
• #1004 Max Consecutive Ones III — variable window that shrinks whenever it holds more than k zeroes.
• #1493 Longest Subarray of 1's After Deleting One Element — variable window allowing at most one zero.
• #1343 Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold — fixed window, count how often the sum clears k * threshold.
• #209 Minimum Size Subarray Sum — grow until the sum reaches the target, then shrink to find the shortest window.
• #3 Longest Substring Without Repeating Characters — variable window with a set or last-seen map.
• #239 Sliding Window Maximum — fixed window, but tracking the max element needs a monotonic deque.

FAQ