LESSON 238 OF 415 · PARTIAL SUMS #1

Longest Subarray with Sum at Most S in Swift: O(n²) Brute Force

Practice O(n²) Read the full explanation

Given an array of positive integers and a number S, find the longest contiguous subarray having the sum at most S.

Return the start and end indices denoting this subarray.

Example

Input: nums = [3, 2, 5, 2, 2, 1, 1, 3, 1 , 2], S = 11
Output: [3, 8]
Explanation:the subarray nums[3...8] of sum 10

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.

STEP 1 OF 10

Guided

Ctrl + Enter to check

SWIFT · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Swift, explained

Problem overview

The method longestSubarray receives an array nums of positive integers and a number S. It must find the longest contiguous subarray whose sum is at most S, and return its first and last index as [start, end].

In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The subarray at indices 3 to 8 is 2, 2, 1, 1, 3, 1. It has six elements and a sum of 10, which is within the limit. No window of seven elements fits under 11, so the answer is [3, 8].

The statement allows O(n²) time and O(1) extra space, which is what a double loop over starts and ends costs.

Approach: every start, every end, one running sum

A subarray is determined by where it starts (i) and where it ends (j). The plan is to try every start. For each start, extend the end one element at a time and keep a running sum. After each extension, check two things: the sum is still at most S, and the subarray is longer than the best one found so far.

The running sum is what keeps the cost at O(n²). Extending the end by one element needs a single addition, because the new sum is the old sum plus nums[j]. Recomputing the sum of nums[i...j] from scratch for every pair would add another loop and make it O(n³).

Take [3, 1, 2] with S = 3. Starting at index 0, the sums are 3 (valid, length 1), 4 (too big) and 6 (too big). Starting at index 1, the sums are 1 (valid, but length 1 does not beat 1), 3 (valid, length 2, a new best, so the answer becomes [1, 2]). Starting at index 2, the sum is 2 (length 1, not better). The final answer is [1, 2].

A faster solution exists, and it relies on the numbers being positive; this lesson stays with the simple double loop.

Step by step

Create answer as an empty [Int](). It will hold the two indices of the best subarray found so far. Each time a longer one is found, it is replaced.
Create maxLen at 0. It is the length of the best subarray found so far. With 0, the first valid subarray of any length is an improvement.
Loop over the start i from 0 up to but not including nums.count.
Create sum at 0 inside this loop. It is the sum of nums[i...j], and it has to start over for every new i. Declaring it inside the outer loop does that automatically.
Loop over the end j from i to the last index. Beginning at i makes the one-element subarray nums[i] the first one tried.
Add nums[j] to sum. Now sum is the sum of the current subarray.
Check both conditions with &&: the sum is at most S, and maxLen is less than the current length, j - i + 1. The length is the number of indices from i to j inclusive.
Update maxLen to the new length.
Set answer to [i, j].
Return answer after both loops.

The solution in Swift

class Solution {
    func longestSubarray(_ nums: [Int], _ S: Int) -> [Int] {
        var answer = [Int]()
        var maxLen = 0
        for i in 0..<nums.count {
            var sum = 0
            for j in i..<nums.count {
                sum += nums[j]
                if sum <= S && maxLen < (j - i + 1) {
                    maxLen = j - i + 1
                    answer = [i, j]
                }
            }
        }
        return answer
    }
}

The Swift details worth knowing:

Half-open ranges. 0..<nums.count stops before count, so the last index used is count - 1. i..<nums.count is never a backwards range, because i is at most count - 1.
A capital parameter name. The parameter is called S. Swift is case-sensitive, and S is an ordinary Int parameter here.
&& short-circuits. If sum <= S is false, the length comparison is not evaluated. Both sides are cheap, so this only matters for how you read the condition.
var for state that changes. answer, maxLen and sum all change after they are created, so none of them can be a let.
Arrays are values. answer = [i, j] replaces the whole array with a new one; nothing else refers to the old one.

Complexity

Time: O(n²). For each of the n starts, the inner loop visits up to n - i ends and does a constant amount of work for each, so the total is about n² / 2 steps.

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

Because every number is positive, the sum only grows as j moves right. Once it passes S, no longer subarray from the same start can fit, so you could stop the inner loop there with break. That saves work, but the worst case is still O(n²). For example, when S is very large, every pair is visited anyway.

Edge cases and common mistakes

No valid subarray. If every element is larger than S, nothing ever passes the check. For [5, 6, 7] with S = 4, the method returns an empty array, []. The caller should be ready for that.
The whole array fits. [1, 2, 3] with S = 100 returns [0, 2].
Ties. Because the comparison is strict (maxLen < ...), the first of several equally long subarrays is kept. For [2, 2, 2] with S = 4 the result is [0, 1].
Sum exactly equal to S. "At most" includes equality. For [4, 1, 1, 4] with S = 2, the subarray [1, 1] sums to 2 and is valid, so the answer is [1, 2].
Using < instead of <= for the sum. That would reject subarrays whose sum equals S.
Length off by one. The length of nums[i...j] is j - i + 1. Using j - i undercounts by one.
Resetting sum in the wrong place. Declaring it outside the outer loop would carry the old total into the next start.

Testing

nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2], S = 11 gives [3, 8].
nums = [5, 6, 7], S = 4 gives [].
nums = [1, 2, 3], S = 100 gives [0, 2].
nums = [4, 1, 1, 4], S = 2 gives [1, 2].
nums = [3, 1, 2], S = 3 gives [1, 2].

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free