Start learning free

LESSON 237 OF 415 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Swift: Sliding Window in O(n)

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find the contiguous subarray of length exactly k with the maximum sum, and return its first and last indices.

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

    SWIFT · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Swift, explained

    Problem overview

    The method maxSum receives an array of integers nums and a positive integer k. Among all contiguous windows of exactly k elements, it must find the one with the largest sum and return its first and last index as [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 and sums to 16, the largest of all windows. The method returns [4, 6].

    Approach: slide the window instead of re-adding it

    The brute-force way adds up all k elements of every window, which costs O(n * k). But two neighbouring windows share k - 1 elements. Moving the window one step to the right changes only two things: the element at its left end leaves, and a new element enters at its right end.

    So the new sum is the old sum, minus the element that left, plus the element that arrived:

    sum = sum - nums[i - 1] + nums[i + k - 1]

    That takes constant time, no matter how big k is. Compute the first window's sum once with a plain loop, then slide across the array and update the sum in O(1) per step. Each element enters the window once and leaves it once, so the total is O(n).

    On the example, the first window [5, 6, 1] sums to 12. Sliding gives these sums for the starts 1 to 5:

    start ileft outaddedsum
    1529
    2669
    31614
    42416
    56313

    The best sum, 16, comes at start 4, so the answer is [4, 6].

    Step by step

    1. Create answer holding the first window's bounds, [0, k - 1]. If no later window beats the first, this is already correct. Starting with an empty array would return nothing whenever the first window is the best one.
    2. Create sum at 0. It will track the sum of the current window.
    3. Add the first k elements with a loop over the indices 0..<k. Now sum is the first window's total.
    4. Create maxSum from sum. The first window is the best seen so far, and it is a real window, so there is no need for a sentinel like Int.min.
    5. Set up a while loop with i starting at 1. The loop runs while i <= nums.count - k, which is the last valid start, and i += 1 goes at the bottom of its body.
    6. Slide the window by subtracting nums[i - 1], the element that just left, and adding nums[i + k - 1], the one that just entered.
    7. Compare with the best. If sum is strictly greater than maxSum, save it and set answer to [i, i + k - 1]. The strict comparison keeps the earliest window when sums tie.
    8. Return answer after the loop.

    The solution in Swift

    class Solution {
    func maxSum(_ nums: [Int], _ k: Int) -> [Int] {
        var answer = [0, k - 1]
        var sum = 0
        for i in 0..<k {
            sum += nums[i]
        }
        var maxSum = sum
        var i = 1
        while i <= nums.count - k {
            sum = sum - nums[i - 1] + nums[i + k - 1]
            if sum > maxSum {
                maxSum = sum
                answer = [i, i + k - 1]
            }
            i += 1
        }
        return answer
    }
}

    The Swift details worth knowing:

    • Two different i variables. The i in the for loop exists only inside that loop. After it ends, var i = 1 declares a new variable with the same name, which Swift allows because the first one is out of scope.
    • while and the manual counter. The loop variable must change by hand, with i += 1. Swift has no ++ operator. If the increment is skipped, the loop never ends.
    • Type inference. [0, k - 1] is inferred as [Int], which matches the return type, and answer is a var because it gets replaced later.
    • A method and a variable called maxSum. Inside the method, the name maxSum means the local variable. That is legal.
    • Invalid k. If k is larger than nums.count, the first loop reads past the end of the array and the program stops with a run-time error. Swift checks array indices. The lesson's tests keep k within the array.

    Complexity

    Time: O(n). The first loop does k additions and the while loop runs n - k times with a constant amount of work each, so the total is about n steps.

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

    Edge cases and common mistakes

    • k equals the array length. The condition 1 <= nums.count - k is false at the start, so the loop body never runs and the answer stays [0, k - 1].
    • k is 1. Each window is a single element. [-3, -1, -2] with k = 1 gives [1, 1].
    • Ties. In [2, 2, 2, 2] with k = 2 every sum is 4, and the result is the first window, [0, 1].
    • Negative numbers. Starting maxSum from the first window, not from 0, handles inputs where every window sum is negative.
    • Wrong index leaving or entering. The element that leaves is nums[i - 1], and the element that enters is nums[i + k - 1]. Using nums[i + k] is off by one and reads past the end on the last window.
    • Loop bound. Using i < nums.count - k instead of <= skips the last window. For [1, 2, 3, 10] with k = 2, the best window [3, 10] would never be checked.
    • Putting i += 1 before the slide. The two statements use i, so the increment belongs at the bottom of the body.

    Testing

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