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 first and last indices as [start, end]. The statement asks for O(n) time and O(1) extra space.
In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11. The answer is [3, 8]: the elements at indices 3 to 8 are 2, 2, 1, 1, 3, 1, which sum to 10 and make a window of length 6. Adding the next element, 2, would give 12, which is over the limit. No run of 7 elements fits within 11.
Approach: a window that only moves right
The brute-force way tries every start index and extends the run to the right, recomputing sums as it goes. That is O(n²). The faster way uses a fact about positive numbers: adding an element always makes a sum larger, and removing one always makes it smaller.
Keep a window of consecutive elements from index first up to, but not including, last, plus the running sum of that window. For each start first:
- Push
lastforward while the next element still fits, that is, whilesum + nums[last] <= S. - The window is now as long as it can be for this start. Record it if it beats the best so far.
- Move the start forward: subtract
nums[first]fromsum.
The key point is that last is never reset. If the window from first reached last, then from first + 1 it reaches at least as far, since the window only lost an element and the sum can only drop. Every element enters the window once and leaves it once, so the total work is linear.
On the example, the window starting at 0 takes 3, 2, 5 (sum 10) and stops, because the next 2 would make 12. It starts at index 1 with sum 7 and takes 2, 2 (sum 11, indices 1 to 4), then stops. The best so far is length 4. Later starts reach [3, 8] with length 6, which no later start beats.
Step by step
- Declare
answeras anumber[]holding[0, 0]. This placeholder is replaced the first time a valid window is found. - Declare
maxLen,sumandlastin onelet, all 0. They hold the best length so far, the window's sum, and the index of the next element to try. - Loop over each start index
first.lastis declared outside this loop on purpose, so it keeps its place whenfirstmoves. - Grow the window with a
whileloop whilelast < nums.length && sum + nums[last] <= S. The bounds check comes first, and&&stops evaluating when it fails, sonums[last]is never read past the end. - Add
nums[last]tosumto put the element in the window. - Record the length if it is a new best. The window covers
firstthroughlast, so its length islast - first + 1. WhenmaxLenis smaller, updatemaxLenand setanswerto[first, last]. Using<rather than<=keeps the leftmost window when two have the same length. - Increment
lastto try the next element. - After the
whileloop, subtractnums[first]fromsum, since the window is about to slide one step to the right. - Return
answerafter theforloop.
The solution in TypeScript
class Solution {
longestSubarray(nums: number[], S: number): number[] {
let answer: number[] = [0, 0];
let maxLen = 0, sum = 0, last = 0;
for (let first = 0; first < nums.length; first++) {
while (last < nums.length && sum + nums[last] <= S) {
sum += nums[last];
if (maxLen < last - first + 1) {
maxLen = last - first + 1;
answer = [first, last];
}
last++;
}
sum -= nums[first];
}
return answer;
}
}
The TypeScript details worth knowing:
- Several variables in one
let.let maxLen = 0, sum = 0, last = 0;declares three variables. Each is inferred as anumber. - Return type.
number[]is an array of numbers. The method returns a new two-element array each time it improves, replacinganswerinstead of changing it. - Reading past the end. TypeScript does not stop
nums[nums.length]: at run time it givesundefined, andsum + undefinedisNaN. A comparison withNaNis always false, so the loop would stop by accident. The explicitlast < nums.lengthtest keeps the code correct on purpose. - Numbers and precision. Sums stay exact as long as they stay below 2^53 (about 9 * 10^15), which is far above any realistic input here.
- A window that is momentarily empty. If
nums[first]alone is larger thanS, thewhileloop adds nothing, andlastmay sit behindfirst. The code subtractsnums[first]anyway, sosumis temporarily negative. It still equals the sum of the elements fromfirstup tolastcounted with a sign, and whenlastcatches up, the arithmetic comes out right. Fornums = [5, 1]andS = 3, the code returns[1, 1].
Complexity
Time: O(n). first goes from 0 to n - 1 once, and last only moves forward, from 0 to at most n. Across the whole run, the while body executes at most n times, so the total is about 2n steps.
Space: O(1). The code keeps a few numbers and one two-element array. It doesn't create a prefix-sum array or copy any part of the input.
Edge cases and common mistakes
- The whole array fits.
[1, 2, 3]withS = 100gives[0, 2]. The window grows once and never shrinks. - Ties.
[2, 2, 2]withS = 4has two windows of length 2. Because of the strict<, the leftmost wins:[0, 1]. - Single elements bigger than
S. In[9, 9, 1, 1, 9]withS = 2, the answer is[2, 3]. The large values can't be in any window. - No valid subarray. For
[5]withS = 3, nothing fits, and the method returns the placeholder[0, 0], which looks like a window of one element. The code has no separate way to say "no window". - An empty array. The loop never runs, and the placeholder is returned.
- Resetting
lastorsumfor every start. That throws away the saved work and turns the algorithm back intoO(n²). - Negative numbers. The method relies on positive values. With negatives, a longer window could have a smaller sum, so moving
lastonly forward misses valid windows. - Using
<=in the length check. It returns the last of several equal-length windows instead of the first.
Testing
nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2],S = 11gives[3, 8].nums = [1, 2, 3],S = 100gives[0, 2].nums = [2, 2, 2],S = 4gives[0, 1].nums = [9, 9, 1, 1, 9],S = 2gives[2, 3].nums = [5, 1],S = 3gives[1, 1].