Start learning free

LESSON 213 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in TypeScript: Sliding Window

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find out the maximum sum of a contiguous subarray of length exactly k

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: 4 6
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 8
    Ctrl + Enter to check

    TYPESCRIPT · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in TypeScript, explained

    Problem overview

    The method maxSum receives an array nums of integers and a positive integer k. It looks at every continuous subarray of length exactly k and returns the first and last index of the one with the largest sum, as [start, end].

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the window 6, 6, 4 at indices 4 to 6 has the largest sum, 16, so the result is [4, 6].

    Approach: slide the window instead of re-adding it

    The straightforward solution adds up the k elements of every window, which costs O(n * k). But two neighbouring windows share k - 1 elements. The window starting at i - 1 covers indices i - 1 to i + k - 2, and the window starting at i covers i to i + k - 1. Moving from one to the next drops the element at i - 1 and picks up the element at i + k - 1.

    So the new sum is the old sum, minus the element that left, plus the element that entered. That is two operations for each window, however large k is. This technique is called a sliding window. You compute the first window directly, then slide it across the array once.

    On the example, the first window 5, 6, 1 sums to 12. Sliding to the next window removes 5 and adds 2: 12 - 5 + 2 = 9, which is the sum of 6, 1, 2. Sliding again removes 6 and adds 6, giving 9. Then the sums go 14, 16 and 13, and 16 is the best.

    Step by step

    1. Start with the first window as the answer. answer is [0, k - 1]. If no later window beats the first, this is already correct. An empty initial answer would return nothing in that case.
    2. Prepare sum, starting at 0, for the sum of the current window.
    3. Add up the first window with a loop over indices 0 to k - 1. This is the only place where k elements are added together.
    4. Record the best sum so far. maxSum starts equal to sum, because the first window is the only one seen.
    5. Loop over the remaining starts, from 1 to nums.length - k inclusive. The comparison is <=, because the last window starts at nums.length - k.
    6. Slide the window. Subtract nums[i - 1], which just left, and add nums[i + k - 1], which just entered.
    7. Compare. When the new sum is strictly greater than maxSum, update maxSum and set answer to [i, i + k - 1]. With a strict >, ties keep the earliest window.
    8. Return answer when the loop is over.

    The solution in TypeScript

    class Solution {
    maxSum(nums: number[], k: number): number[] {
        let answer: number[] = [0, k - 1];
        let sum = 0;
        for (let i = 0; i < k; i++) {
            sum += nums[i];
        }
        let maxSum = sum;
        for (let i = 1; i <= nums.length - k; i++) {
            sum = sum - nums[i - 1] + nums[i + k - 1];
            if (sum > maxSum) {
                maxSum = sum;
                answer = [i, i + k - 1];
            }
        }
        return answer;
    }
}

    Some TypeScript details:

    • Two loops, both named i. Each let i is scoped to its own for statement, so the second loop starts fresh. Reusing the name is fine.
    • Inferred types. let sum = 0 is inferred as number, and let maxSum = sum copies that type. Only answer needs an annotation, to say it is an array of numbers.
    • The loop bound is an expression. nums.length - k is recomputed on each check. That costs almost nothing, but you could store it in a const if you prefer.
    • No integer overflow. TypeScript numbers are doubles, so repeated adding and subtracting cannot wrap around. Whole numbers stay exact as long as every value stays below 2^53, far beyond the sums in this lesson.
    • Reassigning with one expression. sum = sum - nums[i - 1] + nums[i + k - 1] reads the old sum on the right before assigning the new one, so no temporary variable is needed. sum += nums[i + k - 1] - nums[i - 1] is an equivalent shorter form.

    Complexity

    Time: O(n). The first loop does k additions and the second does about n - k slides, each with a constant amount of work. In total, each element enters the window once and leaves once.

    Space: O(1). The method keeps a few numbers and the two-element answer.

    Edge cases and common mistakes

    • The first window is best. For [9, 1, 1] and k = 2 the answer is [0, 1], which is why answer starts as the first window.
    • k equals the length. For [7, 1] and k = 2 the second loop does not run, since nums.length - k is 0 and it starts at 1. The method returns [0, 1].
    • Ties. For [4, 4, 4] and k = 2 both windows sum to 8, and the result is [0, 1].
    • Negative values. For [-3, -1, -2] and k = 1 the result is [1, 1]. Because maxSum starts from the first window's real sum rather than 0, negative sums work.
    • Off-by-one in the entering element. The element that enters the window starting at i is nums[i + k - 1]. Using nums[i + k] reads one position too far, and for the last window it would read undefined and turn the sum into NaN.
    • Using < instead of <= in the second loop. The last window would never be checked, and the answer could miss it even when it is the best one.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3] with k = 3 gives [4, 6].
    • [9, 1, 1] with k = 2 gives [0, 1].
    • [4, 4, 4] with k = 2 gives [0, 1].
    • [-3, -1, -2] with k = 1 gives [1, 1].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free