Problem overview
The method longestSubarray receives an array nums of positive integers and a number S. It must find the longest continuous subarray whose sum is at most S, and return its first and last index as [start, end].
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]. Its sum is 10, which is at most 11, and its length is 6. No longer subarray stays within 11, so the answer is [3, 8].
The statement allows O(n²) time and O(1) extra space. That is enough room to try every possible start and extend it one element at a time.
Approach: for each start, grow the subarray
A subarray is fixed by its start i and its end j. The simplest approach is to look at every pair. A naive version would add up nums[i..j] from scratch for each pair, which costs O(n³). The trick that brings it to O(n²) is to keep a running sum for the current start. When j moves one step to the right, the sum of nums[i..j] is the previous sum plus nums[j], a single addition.
For every pair that passes the test "sum is at most S", we compare its length, j - i + 1, with the longest found so far. The pair is added to the answer only if it is strictly longer, so on ties the first subarray found stays.
The elements are positive, so once the sum for a start goes above S, every longer subarray from that start is also above S. This version doesn't use that fact to stop early: it simply keeps checking, which is still within the allowed O(n²). The positivity matters for faster solutions, which can slide a window.
On the example, the start i = 3 gives running sums 2, 4, 5, 6, 9, 10 and then 12. The first six are within 11, so the best length for that start is 6, and the sum 12 for the seventh element is rejected.
Step by step
- Prepare the answer.
answeris an emptynumber[]that will hold the two indices of the best subarray found so far. - Prepare the best length.
maxLenstarts at 0. Any valid subarray has at least one element, so the first one found is longer than 0 and replaces it. - Loop over starts with
ifrom 0 whilei < nums.length. - Reset the sum for each start.
sumis declared inside the loop, so it begins at 0 every time. - Loop over ends with
jfromi. Starting atimakes the one-element subarraynums[i]the first candidate for that start. - Extend the sum by adding
nums[j]. Nowsumequals the sum ofnums[i..j]. - Test the candidate. It must satisfy both
sum <= SandmaxLen < j - i + 1, joined with&&. The second expression is the length, because both ends are included. - Record the length by setting
maxLentoj - i + 1. - Record the indices by setting
answerto the new array[i, j]. - Return
answerafter both loops end.
The solution in TypeScript
class Solution {
longestSubarray(nums: number[], S: number): number[] {
let answer: number[] = [];
let maxLen = 0;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length; j++) {
sum += nums[j];
if (sum <= S && maxLen < j - i + 1) {
maxLen = j - i + 1;
answer = [i, j];
}
}
}
return answer;
}
}
Some TypeScript details:
- A capital parameter name.
Sis an ordinary parameter. Names are case-sensitive, soSandswould be different identifiers. - Short-circuit
&&. Ina && b, the second operand is evaluated only when the first is true. Here both are cheap, so the order only affects readability. - Replacing, not mutating.
answer = [i, j]creates a new array each time a longer subarray is found. The returned array is never shared with anything else. - Annotation on the empty array.
let answer: number[] = [];says what the array will hold. The annotation is erased when the code is compiled to JavaScript.
Complexity
Time: O(n²). The outer loop runs n times and the inner loop runs up to n times, with a constant amount of work in each step. In total, about n * (n + 1) / 2 pairs are checked.
Space: O(1). The method keeps a few numbers and the two-element answer.
Edge cases and common mistakes
- No valid subarray. If every element is larger than
S, nothing passes the test and the method returns[]. For[5, 6]andS = 4that is the result. - The whole array fits. For
[1, 2, 3]andS = 100the answer is[0, 2]. - Ties. For
[2, 1, 1, 2]andS = 2, the subarrays[1, 1]and the single elements are valid, and the longest has length 2, at indices 1 to 2. The result is[1, 2]. If two subarrays had the same length, the one with the earlier start would win because of the strict<. - Not resetting the sum. Declaring
sumoutside the outer loop makes each start continue the previous total, and valid subarrays get missed. - Length off by one. The length of
nums[i..j]isj - i + 1, notj - i. - Using
< S. The statement says "at most", so a sum equal toScounts. For[4]andS = 4the answer is[0, 0].
Testing
[3, 2, 5, 2, 2, 1, 1, 3, 1, 2]withS = 11gives[3, 8].[5, 6]withS = 4gives[].[1, 2, 3]withS = 100gives[0, 2].[2, 1, 1, 2]withS = 2gives[1, 2].[4]withS = 4gives[0, 0].