Problem overview
The method longestSubarray receives an array nums of positive integers and a limit S. It must find the longest contiguous run of elements whose sum is at most S, and return its start and end indices, both inclusive, as a two-element array.
In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The elements from index 3 to index 8 are 2, 2, 1, 1, 3, 1. They add up to 10, and no longer run stays within 11, so the answer is [3, 8]. The statement asks for O(n) time and O(1) extra space.
Approach: a window that only moves right
The brute force tries every start and every end and adds up each run, which takes O(n²) time at best with running sums. It repeats work: the runs starting at first and at first + 1 share almost all their elements.
Because every number is positive, removing an element from the front of a valid window leaves a valid window. So if the window first ..< last fits within S, then the run that starts at first + 1 can reach at least as far to the right. The right end never needs to move back. The code keeps last where it is, removes nums[first] from the sum, and tries to grow the window again.
Every element enters the window once and leaves it once, so the work is O(n) even though there are two nested loops.
Step by step
- Prepare the answer.
var answer = [0, 0]is a placeholder. It is replaced as soon as a valid run is found. - Declare the window state. One statement,
var maxLen = 0, sum = 0, last = 0, creates the best length so far, the sum of the window, and the index of the next element to try. The window isfirstup to, but not including,last. - Loop over start positions:
for first in 0..<nums.count. The variablelastis declared outside this loop on purpose, so it keeps its value whenfirstadvances. - Grow the window with
while last < nums.count && sum + nums[last] <= S. The bounds check comes first, and&&stops evaluating as soon as it is false, sonums[last]is never read past the end. - Add the element:
sum += nums[last]. - Record a longer run. The window now covers
firstthroughlast, with lengthlast - first + 1. If that beatsmaxLen, store the new length and setanswer = [first, last]. Using<and not<=keeps the leftmost run when two have the same length. - Move on with
last += 1, still inside the inner loop. - Slide the window. After the inner loop, subtract
nums[first]fromsum, since the next iteration starts one position to the right. - Return
answerafter the outer loop.
The solution in Swift
class Solution {
func longestSubarray(_ nums: [Int], _ S: Int) -> [Int] {
var answer = [0, 0]
var maxLen = 0, sum = 0, last = 0
for first in 0..<nums.count {
while last < nums.count && sum + nums[last] <= S {
sum += nums[last]
if maxLen < last - first + 1 {
maxLen = last - first + 1
answer = [first, last]
}
last += 1
}
sum -= nums[first]
}
return answer
}
}
On the example, the answer is replaced four times. The runs found are [0, 2] (sum 10), then [1, 4] (sum 11), then [2, 6] (sum 11), and finally [3, 8] (sum 10). After that no start position gives a longer run, and the method returns [3, 8].
Swift details to notice:
- Half-open ranges.
0..<nums.countexcludes the upper bound. It is empty when the array is empty, so an empty input runs no iterations. (A range whose upper bound is below its lower bound is an error that stops the program, which doesn't apply here.) - Several variables in one
var.var maxLen = 0, sum = 0, last = 0declares three independentIntvariables. - No
++. Swift useslast += 1. - Arrays are values.
answer = [first, last]assigns a fresh array. Nothing else shares it, so there is no aliasing to worry about. - Overflow traps.
sumis anIntof 64 bits and the addition would crash the program on overflow instead of wrapping. Realistic inputs stay far from that limit.
Complexity
Time: O(n). The index last only moves right, and it makes at most n moves in total, across all iterations of the outer loop. The outer loop itself makes n iterations. The sum is updated in constant time instead of being recomputed.
Space: O(1). The code uses a handful of integers and one two-element result array.
Edge cases and common mistakes
- The whole array fits.
[1, 2, 3]withS = 100returns[0, 2]. - Ties.
[2, 2, 2, 2]withS = 4returns[0, 1], the leftmost of the runs of length 2. - Elements above
S. Whennums[first]is itself bigger thanS, the window is empty andlastequalsfirst. The subtraction then makessumnegative, and the next iteration, which starts withlaststill on that element, adds it back and brings the sum to the right value.[5, 1]withS = 4returns[1, 1]. - No valid run at all.
[5, 6]withS = 4returns the placeholder[0, 0], which looks the same as a real answer for a single element at index 0. The lesson's tests don't distinguish them, and a caller that needs to know should checkmaxLen. - Empty array. The loop never runs, and the placeholder
[0, 0]comes back. - Checking the bounds second. Writing the loop condition as
sum + nums[last] <= S && last < nums.countreads past the end of the array and crashes the program. - Resetting
last. Movinglastback tofirston each iteration would make the algorithmO(n²). - Forgetting to subtract. If
nums[first]isn't removed fromsum, the window keeps counting elements it no longer contains.
Testing
[3, 2, 5, 2, 2, 1, 1, 3, 1, 2]withS = 11gives[3, 8].[1, 2, 3]withS = 100gives[0, 2].[2, 2, 2, 2]withS = 4gives[0, 1].[5, 1]withS = 4gives[1, 1].[4]withS = 4gives[0, 0].
