Start learning free

LESSON 212 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in TypeScript: Brute Force

Practice O(n * k) 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. Among all continuous subarrays of length exactly k, it must find the one with the largest sum, and return its first and last index as a two-element array [start, end].

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the window at indices 4 to 6 holds 6, 6, 4, which sums to 16, the largest of all windows of three. The method returns [4, 6].

    Approach: add up every window

    A window of length k is fixed by where it starts. If it starts at index i, it covers indices i to i + k - 1. The last window must still fit in the array, so the last start is nums.length - k. An array of length n therefore has n - k + 1 windows.

    The brute-force idea is direct: for each start, add up the k elements of its window, and remember the best sum together with the indices that produced it. It does the same additions again and again for overlapping windows, which is wasteful, and the next lesson on this problem removes that waste. Here the goal is a correct, simple version first.

    Here is the search on the example. The windows of length 3 and their sums are:

    start 0: 5 + 6 + 1 = 12
start 1: 6 + 1 + 2 = 9
start 2: 1 + 2 + 6 = 9
start 3: 2 + 6 + 6 = 14
start 4: 6 + 6 + 4 = 16
start 5: 6 + 4 + 3 = 13

    There are 8 - 3 + 1 = 6 windows, and the largest sum is 16 at start 4.

    Look at starts 3 and 4 above: the two windows share the elements 6 and 6, yet the brute force adds them twice. Each window differs from its neighbour by one element leaving and one entering. Spotting that overlap is the whole idea behind the faster solution, which updates the sum in constant time per window.

    Step by step

    1. Track the best sum. maxSum starts at Number.NEGATIVE_INFINITY, which is smaller than any real sum, so the first window always replaces it. Starting at 0 would fail when every window sum is negative.
    2. Prepare the answer. answer is an empty number[]. It will hold the two indices of the best window so far.
    3. Loop over window starts with i from 0 up to nums.length - k, inclusive. The condition is <=, because a window starting at nums.length - k ends exactly at the last element.
    4. Reset the sum for each window: sum is declared as 0 inside the loop.
    5. Loop over the window. The inner index idx runs from i while idx < i + k, which visits exactly k positions.
    6. Add nums[idx] to sum.
    7. Compare. If sum is strictly greater than maxSum, update maxSum and replace answer with [i, i + k - 1]. The strict comparison means that when two windows tie, the earlier one stays.
    8. Return answer after the loops.

    The solution in TypeScript

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

    Some TypeScript details:

    • The local variable shares the method's name. The method is maxSum and the variable inside it is also maxSum. That is legal: the method lives on the class and is reached with this.maxSum, while the variable is local to the body. It can confuse readers, so a name such as best would be clearer in your own code.
    • The empty array needs its annotation. With the annotation let answer: number[] = []; the variable has a clear type. Without it, let answer = [] would be typed from later assignments, which is less obvious.
    • Replace, don't mutate. answer = [i, i + k - 1] makes a new array each time a better window appears. The old arrays are simply dropped.
    • Inclusive indices. A window [i, i + k - 1] is inclusive on both ends. Remember that when you use the result: with [4, 6] and k = 3, the window holds three elements, nums[4], nums[5] and nums[6].

    Complexity

    Time: O(n * k). There are n - k + 1 windows, and each costs k additions. When k is about half of n this is quadratic. When k is 1 or equals n, it is linear.

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

    Edge cases and common mistakes

    • Ties. For [4, 4, 4] and k = 2 the method returns [0, 1], the earliest window, because the second window's equal sum does not pass the strict >.
    • The last window. For [9, 1, 1] and k = 2 the loop must reach start 1. Writing i < nums.length - k would stop at start 0 and never try [1, 1].
    • All negative. For [-3, -1, -2] and k = 1 the answer is [1, 1], the single element -1. This only works because maxSum starts at negative infinity.
    • k equal to the length. For [7, 1] and k = 2 there is one window, and the method returns [0, 1].
    • Forgetting to reset sum. If sum is declared outside the outer loop, every window adds on top of the previous one.
    • Window longer than the array. If k is larger than nums.length, the loop never runs and the method returns []. The lesson's inputs don't do this.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3] with k = 3 gives [4, 6].
    • [4, 4, 4] with k = 2 gives [0, 1].
    • [9, 1, 1] 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