Problem overview
LongestSubarray(nums, S) receives an array of positive integers and a limit S. It must find the longest contiguous subarray whose sum is at most S and return its start and end indices as a two-element array.
In the example, nums = [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] with a sum of 10, and no longer subarray stays within 11, so the answer is [3, 8]. The note sets the budget: O(n) time and O(1) extra space.
Approach: slide a window that never exceeds S
The brute-force method tries every start and every end and sums each range, which is O(n²) pairs at least. The faster idea uses the fact that all numbers are positive. Adding an element to a subarray always raises its sum, and removing one always lowers it. So for each possible start, the best end can be found by growing the window to the right until the next element would break the limit.
The key observation is that the end never has to move back. If the window from first to last - 1 fits within S, then after dropping nums[first], the window starting at first + 1 and ending at last - 1 fits too, because it is smaller. The search for the next start can therefore continue from the same last. Both indices only move forward, so every element enters the window once and leaves once, which gives O(n) overall.
This lesson keeps the window as nums[first..last-1] and the variable last is the next element to try, so it is one past the right end of the window.
Step by step
- Prepare the answer.
answeris anint[]of size 2. C# fills a new array with zeros, so it starts as[0, 0], a placeholder replaced once a valid subarray is found. - Declare the state.
maxLenis the longest length so far,sumis the window's sum, andlastis the index of the next element to try. All three areints starting at 0, declared in one statement. - Loop over start positions.
firstruns from 0 up tonums.Length - 1.lastis declared outside this loop on purpose: whenfirstmoves, the window keeps its right end. - Grow the window. The inner
whileloop continues whilelast < nums.Lengthandsum + 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 new best. The window now covers
firstthroughlast, so its length islast - first + 1. If that beatsmaxLen, updatemaxLenand setanswertonew int[]{first, last}. The strict<keeps the leftmost subarray when two have equal length. - Move on:
last++. - Slide the start. After the
whileloop, subtractnums[first]fromsum, because the next iteration starts one position to the right. - Return
answerafter theforloop.
The solution in C#
class Solution {
public int[] LongestSubarray(int[] nums, int S) {
int[] answer = new int[2];
int maxLen = 0, sum = 0, last = 0;
for (int 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 = new int[]{first, last};
}
last++;
}
sum -= nums[first];
}
return answer;
}
}
Some C# details are worth a closer look:
- Arrays are zero-filled.
new int[2]holds{0, 0}. The array's length is fixed at 2, andanswer = new int[]{first, last}replaces the whole array with a new one instead of changing its elements. Length, notCount. Arrays report their size through theLengthproperty.Countbelongs to collections such asList<int>.- Short-circuit
&&. The right-hand side runs only when the left-hand side is true. Reversing the two conditions would throw anIndexOutOfRangeExceptionwhenlastreachesnums.Length. - Several variables in one declaration.
int maxLen = 0, sum = 0, last = 0;declares three separateints, each with its own initial value. - A subtle case. If
nums[first]alone is bigger thanS, the window is empty andlastequalsfirst, yetsum -= nums[first]still runs, sosumbecomes negative. The next iteration then letslastpass over that element again: the inner loop addsnums[last]back, which bringssumback in line with the window. The result is right, but the bookkeeping is delicate.
Tracing the example
For first = 0, the window grows over 3, 2 and 5 (sum 10), and the next 2 would make 12, so it stops with the best [0, 2]. Dropping the 3 leaves a sum of 7. For first = 1, adding 2 and 2 gives 11 and the best [1, 4], and the next element 1 would reach 12. For first = 2, the window extends over 1 and 1 to reach [2, 6]. For first = 3, it adds 3 and 1 and reaches [3, 8], with length 6. No later start does better, and the method returns [3, 8].
Complexity
Time: O(n). The inner while loop does not restart for each first, because last lives outside the for loop. In total last increases at most n times and first increases n times, so the number of steps is at most about 2n.
Extra space: O(1). The code keeps a few integers and a two-element array.
Edge cases and common mistakes
- Equal lengths. For
[2, 2, 2]withS = 4, both[0, 1]and[1, 2]have length 2. The strict<keeps[0, 1]. Writing<=would return the later one. - A limit that fits everything. With a large
S, the window covers the entire array and the answer is[0, nums.Length - 1]. - No valid subarray. If every element is larger than
S, nothing is ever recorded and the method returns the placeholder[0, 0]. That is not a valid subarray, so it's worth knowing what the code does in that case. - Empty array. The loop never runs and the method returns
[0, 0]. - Declaring
lastinside theforloop. Resetting it to 0 on every start turns the algorithm back into the quadratic one. - Forgetting
sum -= nums[first]. The window would keep a stale sum and shrink too early. - Negative numbers. The argument that the end never has to move back relies on positive values. With negatives, removing an element can raise the sum, so the reasoning no longer holds.
Testing
nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2],S = 11gives[3, 8].nums = [1, 2, 3],S = 3gives[0, 1].nums = [2, 2, 2],S = 4gives[0, 1].nums = [5, 1],S = 3gives[1, 1].nums = [4, 1, 1, 1, 9, 1, 1, 1, 1],S = 4gives[5, 8].