Problem overview
The method subarraySum receives an array of non-negative numbers, nums, and a target. It must find a continuous subarray whose elements add up to target and return its first and last index as [start, end]. If several subarrays work, any of them is accepted. If none does, the method returns [-1, -1].
For nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and a target of 21, the answer is [2, 6], because 5 + 2 + 1 + 3 + 10 = 21. The statement requires O(n) time and O(1) extra space, and it promises that every number is non-negative. That promise is what makes the fast solution work.
Approach: a window that grows and shrinks
The brute-force solution tries every start and every end, adding up the elements between them: O(n³), or O(n²) if you keep a running sum for each start. Both are too slow for the lesson's limit.
The faster idea keeps one window, written [j...i], and its running total in sum. Each iteration moves the right end i one step and adds nums[i]. If the total is now too big, you drop elements from the left end j until it fits again, or until only nums[i] remains.
Dropping from the left is safe because nothing is negative. Removing an element can only lower the sum or leave it unchanged, and adding elements can only raise it. So when the sum exceeds the target, no longer window ending at i can ever work, and shrinking from the left is the only move that helps. With negative numbers that argument fails, and a different technique is needed.
On the example, the window grows over 1, 1, 5, 2, 1, 3, 10 to reach a sum of 23, which is above 21. The window drops the first 1 (sum 22), then the second (sum 21), and now j = 2, i = 6 and the sum matches. The method returns [2, 6].
Step by step
- Declare
jandsumwith onelet, both 0. The window starts empty at the left edge. - Loop over
ifrom 0 whilei < nums.length. In every iteration,nums[i]becomes the right end of the window. - Add
nums[i]tosum. The total always describes the elements fromjtoi. - Shrink while the sum is too large. The
whileloop runs whilej < iandsum > target. The conditionj < ikeeps the window from becoming empty, sonums[i]always stays. - Subtract
nums[j]fromsum, because that element leaves the window. - Increment
j. The left edge moves right and never moves back. - Check for a match after the inner loop: if
sum === target, return[j, i]at once. The first window found is the one that ends earliest, and that is a valid answer. - Return
[-1, -1]after the loop, because no window matched.
The solution in TypeScript
class Solution {
subarraySum(nums: number[], target: number): number[] {
let j = 0, sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
while (j < i && sum > target) {
sum -= nums[j];
j++;
}
if (sum === target) {
return [j, i];
}
}
return [-1, -1];
}
}
The TypeScript details worth a closer look:
- One
let, two variables.let j = 0, sum = 0;declares both. TypeScript infersnumberfor each from the initial value, so no annotations are needed. ===compares without conversion. It is the usual choice in TypeScript. Because both sides are numbers here,==would give the same result, but===keeps the habit safe.- The return type is just an array. The signature says
number[], so[j, i]is an ordinary array of two numbers. TypeScript doesn't check that its length is 2, and the annotation disappears when the code is compiled. numberis a double. The sum can't overflow in the way a 32-bit integer can. Integers stay exact up to 2^53, which is far above what these inputs reach.
Complexity
Time: O(n). The outer loop runs n times. The inner loop can look expensive, but j only increases and never passes i, so all the inner iterations together run at most n times. Every element is added once and subtracted at most once.
Space: O(1). The method uses three numbers, i, j and sum, plus the small result array it returns, no matter how large nums is.
Edge cases and common mistakes
- No matching subarray.
[1, 2]with target 7 returns[-1, -1]. - A single element.
[5]with target 5 returns[0, 0], and the same array with target 3 returns[-1, -1]. With one element,j < iis false, so the inner loop never removes the only element. - Zeros.
[0, 0, 3]with target 3 returns[0, 2]. The zeros never make the sum exceed the target, so nothing is dropped, and the window keeps them. With target 0 and[4, 0, 0], the window drops the 4 and returns[1, 1], a valid one-element subarray. - Several valid answers.
[1, 2, 3, 3]with target 6 has two:[0, 2]and[2, 3]. The method returns[0, 2], the first window it meets. Any valid range is accepted. - Dropping the
j < icheck. If the sum is above the target and the window is a single large element, the loop would remove it and leavejpasti, with an empty window. - Using the idea with negative numbers. The reasoning above relies on non-negative values. With negatives, shrinking can miss answers because a later negative element could bring the sum back down.
- Returning values instead of indices. The method returns positions in
nums, not the numbers in the subarray.
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [7, 1, 2],target = 3gives[1, 2].nums = [0, 0, 3],target = 3gives[0, 2].nums = [1, 2],target = 7gives[-1, -1].nums = [],target = 0gives[-1, -1].