Problem overview
The method SubarraySum receives an array nums of non-negative integers and an integer target. It must find a contiguous run of elements, a subarray, whose sum equals target, and return the first and last index of that run as a two-element int[]. If several subarrays qualify, any of them is accepted. If none does, the method returns {-1, -1}.
In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and target = 21. The elements from index 2 to index 6 are 5, 2, 1, 3 and 10, which add up to 21, so the answer is [2, 6].
The statement also sets a budget: O(n) time and O(1) extra space. Checking every start and end pair would cost O(n²) or worse, so we need a way to look at each element a constant number of times.
Approach: a window that only moves right
Because every number is non-negative, adding an element to a subarray never lowers its sum, and removing an element never raises it. That gives us two reliable moves:
- If the sum is too small, extend the subarray on the right.
- If the sum is too large, drop elements from the left.
We keep a window [j...i] and its running total sum. The loop variable i is the right end and extends by one on every pass. The index j is the left end and moves right only when the sum is too big. Neither index ever moves backwards, so together they move at most 2n times, which is O(n). The extra memory is three integers, which is O(1).
This only works because of the non-negative rule. With negative numbers, dropping an element from the left could make the sum bigger, and the window logic would no longer know which way to move.
Here is the example. The window grows through sums 1, 2, 7, 9, 10 and 13. At i = 6 the new element 10 makes the sum 23, which is above 21. The window drops nums[0] (sum 22, j = 1), then nums[1] (sum 21, j = 2). Now the sum matches, and the method returns [2, 6].
Step by step
- Declare the window state.
jis the left end of the window andsumis its total. Both start at 0, and one statement declares both. - Loop over every index
i. Each iteration makesnums[i]the new right end. - Add
nums[i]tosum, because the element now belongs to the window. - Open a
whileloop that shrinks the window whilej < iandsum > target. The conditionj < ikeepsnums[i]inside the window, so the window is never empty. - Subtract
nums[j]fromsum. That element is leaving the window. - Increment
j. The left end moves one place to the right. - Test for a match. After the shrinking loop, and still inside the
forloop, check whethersum == target. If it does, returnnew int[]{j, i}immediately. - Report failure. If the loop ends without a match, return
new int[]{-1, -1}.
The solution in C#
class Solution {
public int[] SubarraySum(int[] nums, int target) {
int j = 0, sum = 0;
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
while (j < i && sum > target) {
sum -= nums[j];
j++;
}
if (sum == target) {
return new int[]{j, i};
}
}
return new int[]{-1, -1};
}
}
A few C# details are worth noticing:
- One declaration, two variables.
int j = 0, sum = 0;declares two separateintvariables, each with its own initial value. - Arrays know their length.
nums.Lengthis a property, so it has no parentheses. A C# array has a fixed length, and the loop conditioni < nums.Lengthstops one step before the first invalid index. - Returning an array.
new int[]{j, i}creates a new two-element array with an initializer. The caller reads the start from index 0 and the end from index 1. - Integer sums.
sumis anint, and C# integer arithmetic wraps around silently when it overflows. For this lesson's sizes that is not a concern, but a very large array of large values could, in principle, exceed the range ofint.
Complexity
Time: O(n). The outer loop runs n times. The inner while loop looks like a nested loop, but j only increases and can never pass n, so across the whole run the inner loop body executes at most n times in total. The total work is at most about 2n steps.
Space: O(1). The method uses i, j and sum, plus the two-element result array, whose size doesn't depend on the input.
Edge cases and common mistakes
- No matching subarray. For
[1, 2, 3]and a target of 100 the window never reaches the target, and the method returns[-1, -1]. An empty array gives the same result, because the loop body never runs. - A single element is a valid subarray. For
[7]and a target of 7, the method returns[0, 0]. - Zeros. The target can be 0 when the array contains zeros. For
[5, 0]and a target of 0, the window ati = 1has sum 5, so the shrinking loop drops the 5 and the method returns[1, 1]. If every element is positive and the target is 0, there is no answer. - A first element that is too big. For
[10, 1, 1]and a target of 2, the first element alone exceeds the target. The guardj < istops the shrinking loop, so the window keeps 10 for now. On the next pass the sum is 11, the loop drops the 10, and the window continues from index 1. The method returns[1, 2]. - Dropping the
j < iguard. Without it,jcould move pastiand the window would have a negative size, withsumout of step with the real contents. - Using
ifinstead ofwhile. One new element may require dropping several old ones, as in the example where two elements leave at once. - Which answer comes back. The method returns the subarray that ends earliest. For
[3, 1, 2]and a target of 3, it returns[0, 0]rather than[1, 2]. Both are valid, and the lesson accepts either.
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [1, 2, 3],target = 100gives[-1, -1].nums = [10, 1, 1],target = 2gives[1, 2].nums = [5, 0],target = 0gives[1, 1].nums = [],target = 0gives[-1, -1].