Start learning free

LESSON 236 OF 415 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Swift: Brute Force in O(n * k)

Practice O(n * k) 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. It looks at every contiguous subarray (a window) of exactly k elements and finds the window with the largest sum. It returns the first and last index of that window as a two-element array, [start, end].

    In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. The window from index 4 to index 6 holds 6, 6, 4 and has the sum 16, more than any other window of three. The method returns [4, 6].

    Approach: add up every window

    An array of n elements has n - k + 1 windows of length k. The first one starts at index 0, and the last one starts at index n - k, because it has to end at the final element.

    The simplest plan follows from that. For each possible start, add up the k elements of its window, compare the sum with the best so far, and keep the best window's bounds. This is a brute-force solution: it does k additions for each of the n - k + 1 windows, so it takes O(n * k) time. It is easy to get right, and the next lesson on this problem improves it by reusing the sum of the previous window.

    On the example, the window sums for the starts 0 to 5 are 12, 9, 9, 14, 16 and 13. The largest is 16, at start 4. The loop reaches it on its fifth pass: maxSum has been 14 until then, 16 is bigger, so answer becomes [4, 6]. The last window, with sum 13, is smaller and changes nothing.

    Step by step

    1. Create maxSum with var, starting at Int.min. It holds the largest window sum seen so far. Window sums can be negative, so starting at 0 would be a mistake. Int.min is the smallest possible Int, so the first window always beats it.
    2. Create answer as an empty [Int] with var. It will hold the two bounds of the best window.
    3. Loop over every window start i from 0 to nums.count - k. The range uses ... because the last start is included.
    4. Create sum at 0 inside the loop. Each window gets its own fresh total.
    5. Loop over the window's positions idx from i up to but not including i + k, which visits exactly k indices.
    6. Add nums[idx] to sum.
    7. Compare after the inner loop. If sum is strictly greater than maxSum, save the new maximum and set answer to [i, i + k - 1]. The strict comparison means that when two windows tie, the earlier one stays.
    8. Return answer after the outer loop.

    The solution in Swift

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

    The Swift details worth knowing:

    • Closed and half-open ranges. 0...(nums.count - k) includes the upper bound, which is what the last window start needs. i..<(i + k) leaves out its upper bound, so it visits k indices. Mixing them up is the classic off-by-one error here.
    • A method and a variable with the same name. The method is called maxSum and so is the local var. That is legal: inside the method, the name refers to the local variable.
    • [Int](). This creates an empty array of integers. Assigning [i, i + k - 1] later replaces it with a new two-element array, so it must be declared with var.
    • Arrays are values. answer = [i, i + k - 1] builds a fresh array each time. Nothing else shares it.
    • A bad range crashes. If k is larger than nums.count, the upper bound of 0...(nums.count - k) is negative and the program stops with a run-time error. A range in Swift cannot run backwards. The lesson's tests keep k within the array.

    Complexity

    Time: O(n * k). There are n - k + 1 windows and each one costs k additions. When k is close to half of n, that is about n² / 4 operations, which is quadratic. When k is 1 or close to n, it is nearly linear.

    Space: O(1) extra. The only extra storage is a few integers and the two-element result.

    Edge cases and common mistakes

    • All negative numbers. For [-3, -1, -2] and k = 1 the answer is [1, 1], since -1 is the largest value. This is why maxSum starts at Int.min and not 0.
    • k equals the array length. There is one window, so [1, 2, 3] with k = 3 returns [0, 2].
    • Ties. In [2, 2, 2, 2] with k = 2 every window sums to 4. The strict > keeps the first one, so the result is [0, 1]. Using >= would return the last window, [2, 3].
    • The end index. The window starting at i ends at i + k - 1, not i + k. Returning i + k is off by one.
    • Not resetting sum. Declaring it outside the outer loop would let the sums of different windows pile up.
    • Windows that run past the end. Looping i up to nums.count - 1 would read past the array on the last starts and crash.

    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 = [-3, -1, -2], k = 1 gives [1, 1].
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free