LESSON 213 OF 338 · PARTIAL SUMS #1

Longest Subarray with Sum at Most S in Go: 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

GO · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Go, explained

Problem overview

The method longestSubarray receives a slice of positive integers, nums, and a number S. It must find the longest contiguous subarray whose sum is at most S and return its start and end indices.

For 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], with sum 10. Adding the next element would make 12, and no six-element or longer window fits in 11 elsewhere, so the answer is [3 8].

The statement allows O(n²) time and O(1) extra space, which is what the nested-loop approach below uses.

Approach: every start, every end

A subarray is determined by its start i and its end j. The idea is to try each start and, for that start, extend the end one element at a time. Keeping a running sum makes each extension a single addition instead of a fresh sum over the whole range.

Whenever the running sum is at most S and the subarray is longer than the best one so far, remember it. Because the numbers are positive, the sum only grows as the end moves right, so once it exceeds S every longer subarray from this start fails too. The reference solution doesn't stop early, though. It keeps scanning, which stays within O(n²).

Step by step

Declare answer as an empty []int. Each time a longer valid subarray appears, it is replaced by a new two-element slice.
Declare maxLen as 0. The first valid subarray, of any length, is longer than that.
Loop over starts. The index i runs while i < len(nums).
Declare sum as 0 inside that loop, so it restarts for each start.
Loop over ends. The index j starts at i, so the single element nums[i] is the first subarray tried.
Add nums[j] to sum. Now sum covers indices i to j.
Test two conditions together: sum <= S (valid) and maxLen < (j-i+1) (longer than the best so far). The length of the range is j-i+1.
Update maxLen to the new length.
Set answer to []int{i, j}.
Return answer after both loops.

The solution in Go

type Solution struct{}

func (this Solution) longestSubarray(nums []int, S int) []int {
    answer := []int{}
    maxLen := 0
    for i := 0; i < len(nums); i++ {
        sum := 0
        for j := i; j < len(nums); j++ {
            sum += nums[j]
            if sum <= S && maxLen < (j-i+1) {
                maxLen = j - i + 1
                answer = []int{i, j}
            }
        }
    }
    return answer
}

Go details:

Methods instead of classes. Go has no classes. Solution is an empty struct, and longestSubarray is a method with the receiver (this Solution). You call it as Solution{}.longestSubarray(nums, S). The name this is only a convention borrowed from other languages; Go programs usually use a short name such as s.
A capital S is just a name. Parameter names can be any identifier. Only a capital first letter on a package-level name changes visibility, and it doesn't matter for a local parameter.
&& short-circuits. If sum <= S is false, the second comparison isn't evaluated.
Redeclaring in a loop is fine. sum := 0 runs on every pass of the outer loop and creates a fresh variable each time.
The empty result. If no subarray qualifies, answer stays []int{}, an empty slice. Check len(answer) before indexing it.

Tracing one start

Take the example and the start i = 3. The running sum grows as j moves: 2 at j = 3, 4 at j = 4, 5, 6, 9 and 10 at j = 8. Each of those is at most 11, and each is longer than the previous best from this start, so the answer is updated at every step and ends as [3 8] with maxLen equal to 6. At j = 9 the sum becomes 12, which is above 11, so the condition fails and the answer stays.

Later starts begin with sum at 0 again. The start i = 4 reaches index 9 with sum 10, which is also length 6. It ties the best but does not beat it, so the strict maxLen < (j-i+1) leaves the answer at [3 8].

Complexity

Time: O(n²). For each of the n starts, the inner loop runs up to n - i times, which adds up to about n²/2 iterations, each with constant work.

Space: O(1). The function uses a few integers and a two-element answer slice.

Edge cases and common mistakes

No valid subarray. For [5, 6] and S = 3, every element alone exceeds S, so the function returns an empty slice.
Everything fits. For [1, 1, 1] and S = 10 the answer is [0 2].
Ties in length. The strict maxLen < (j-i+1) keeps the first subarray of a given length. For [4, 1, 4, 1] and S = 5, the windows [0 1], [1 2] and [2 3] all have length 2, and the function returns [0 1].
Sum equal to S. The condition is <=. For [2, 3] and S = 5 the whole slice qualifies; with < it wouldn't.
Not resetting sum. Declaring sum before the outer loop would carry the previous start's total into the next one.
Length off by one. The number of elements from i to j inclusive is j-i+1, not j-i.
Negative numbers. The problem promises positive values. With negatives, a longer range could fit again after exceeding S; the version here still checks every range, so it stays correct, but an early-stop shortcut wouldn't.

Testing

[3, 2, 5, 2, 2, 1, 1, 3, 1, 2], S = 11 gives [3 8].
[5, 6], S = 3 gives an empty slice.
[1, 1, 1], S = 10 gives [0 2].
[4, 1, 4, 1], S = 5 gives [0 1].
[2, 3], S = 3 gives [0 0].

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

Start learning free