LESSON 282 OF 338 · SLIDING WINDOW

Longest Subarray With Sum At Most S in Go: O(n) Sliding Window

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) time and use O(1) extra space.

STEP 1 OF 9

Guided

Ctrl + Enter to check

GO · SLIDING WINDOW

Longest Subarray With Sum At Most S in Go, explained

Problem overview

The method longestSubarray receives a slice nums of positive integers and a limit S. It must return the start and end indices, as a two-element []int, of the longest contiguous subarray whose sum is at most S.

In the example, nums = []int{3, 2, 5, 2, 2, 1, 1, 3, 1, 2} and S = 11. The subarray from index 3 to index 8 is 2, 2, 1, 1, 3, 1. It has six elements and sums to 10. No subarray of seven elements fits under 11, so the answer is [3, 8].

The statement asks for O(n) time and O(1) extra space.

Approach: a window that never moves backwards

The brute-force way tries every pair of start and end indices and adds up the elements between them. That is O(n²) pairs, and O(n³) if each sum is recomputed. It ignores a useful fact: all numbers are positive.

Because the numbers are positive, adding an element can only increase the sum, and removing one can only decrease it. That makes two things true:

If the window from first to last already fits, you can try to extend it to the right. If the next element doesn't fit, no longer window starting at first does either.
If a window starting at first reaches as far as last - 1, then a window starting at first + 1 can reach at least as far. It has fewer elements to pay for, so its end never needs to go back.

So the right end last only moves forward, and the left end first only moves forward. Each index enters the window once and leaves once, which is O(n) in total, and the only extra memory is a few integers.

In this solution last is the index of the next element to try, so the window holds nums[first] through nums[last - 1], and its sum is kept in sum. Inside the inner loop, right after an element is added, the window ends at last, and that is the moment the length last - first + 1 is measured.

On the example, the windows reached for each value of first are:

first = 0: indices 0 to 2, sum 10 (adding the next 2 would give 12);
first = 1: indices 1 to 4, sum 11;
first = 2: indices 2 to 6, sum 11;
first = 3: indices 3 to 8, sum 10, the first window of six elements;
first = 4: indices 4 to 9, sum 10, also six elements, but it isn't longer than the best, so the answer stays at [3, 8].

Step by step

Start with a placeholder answer, []int{0, 0}. It is replaced as soon as a valid subarray is found.
Declare the state in one statement: maxLen, the best length so far; sum, the window's sum; and last, the next index to try. All start at 0.
Loop over first, the start of the window, from 0 to the end. Every start is tried, but last is declared outside this loop so it keeps its value from one start to the next.
Grow the window with a condition-only for: while last is inside the slice and adding nums[last] keeps the sum at most S. The bound check comes first so that nums[last] is never read past the end.
Add the element to sum.
Record a new best. The window now covers first through last, so its length is last - first + 1. If it beats maxLen, store the length and the pair of indices. The comparison is strict, so on a tie the earliest window is kept.
Advance last to try the next element.
Slide the window once the inner loop stops: subtract nums[first] from sum, because the next iteration of the outer loop starts one position later.
Return answer after the outer loop.

The solution in Go

type Solution struct{}

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

The Go details worth knowing:

No while. The inner loop is a for with only a condition, which is Go's way to write a while loop. The outer for is the usual three-part counting loop.
Short-circuit order. In last < len(nums) && sum+nums[last] <= S, the second part runs only when the first is true. Swapping them would panic with an index out of range error when last reaches len(nums).
Multiple assignment with :=. maxLen, sum, last := 0, 0, 0 declares three int variables at once. Every variable declared with := must be used, or the compiler refuses to build.
Methods on a struct. Go has no classes. Solution is an empty struct and longestSubarray is a method with a value receiver, called as Solution{}.longestSubarray(nums, S). The receiver is named this here, but the name is only a convention.
Fresh slices for the answer. answer = []int{first, last} allocates a new two-element slice each time, so the returned slice is never shared with anything else.
An element larger than S. When nums[first] alone exceeds S, the inner loop adds nothing, last stays put, and sum -= nums[first] makes sum negative. On the next start, last is behind first, and the inner loop first adds that skipped element, which brings sum back to 0 for the empty window. The lengths measured during that catch-up are 0 or negative, so they never replace the answer.

Complexity

Time: O(n). The outer loop runs n times. last goes from 0 to at most n and never decreases, so the inner loop's iterations over the whole run add up to at most n. The total is at most about 2n steps.

Space: O(1). The function uses a few integers and a two-element slice for the answer, whatever the size of the input.

Edge cases and common mistakes

The whole slice fits. nums = []int{1, 2, 3} and S = 100 returns [0, 2].
Ties. nums = []int{2, 2, 2} and S = 4 returns [0, 1], because [1, 2] has the same length and doesn't replace it. With nums = []int{3, 1, 2, 1} and S = 3, the result is [1, 2].
A single element equal to S. nums = []int{4} and S = 4 returns [0, 0], which is a valid subarray.
No subarray fits. When every element is larger than S, there is no valid subarray, and the function returns the placeholder: nums = []int{5, 6} and S = 3 gives [0, 0]. The same happens for an empty slice. If a program needs to tell "nothing fits" from a real answer, it can test whether maxLen is still 0 at the end and return a sentinel such as []int{-1, -1}.
A big element at the start. With nums = []int{5, 1, 1} and S = 3, the first element never fits, but the window can restart after it: the answer is [1, 2].
Using <= instead of < in the best-length check. The answer would move to the last window of the maximum length instead of the first.
Resetting last inside the outer loop. That makes the solution O(n²), because every start would re-scan its window from scratch.
Negative numbers. The reasoning above needs positive numbers. With negatives, a window that doesn't fit could fit after growing further, so this algorithm would give wrong answers.

Testing

nums = []int{3, 2, 5, 2, 2, 1, 1, 3, 1, 2}, S = 11 gives [3 8].
nums = []int{1, 2, 3}, S = 100 gives [0 2].
nums = []int{2, 2, 2}, S = 4 gives [0 1].
nums = []int{5, 1, 1}, S = 3 gives [1 2].
nums = []int{4}, S = 4 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