Problem overview
The method SubarraySum receives an int[] nums and an int target. It must find a contiguous subarray whose elements add up to target and return its start and end indices. If several subarrays qualify, any of them is accepted. The numbers can be positive or negative. The statement asks for O(n) time and O(n) extra space.
In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and the target is 21. The elements at indices 2 to 6 are 5, 2, 1, 3, 10, which add up to 21, so the method returns [2, 6]. When nothing matches, the lesson's solution returns [-1, -1].
Approach: prefix sums and a lookup table
Negative numbers rule out the usual sliding window: when the window's sum is too large, you can't tell whether to shrink it or grow it, because adding a negative number might lower the sum. A different idea works for any numbers.
Let sum be the prefix sum at index i: the total of nums[0..i]. A subarray that ends at i and starts after some earlier prefix has the sum sum - earlier, where earlier is the prefix sum just before the subarray's first element. For this to equal target, you need earlier = sum - target. So at every index you ask one question: have I already seen a prefix with the sum sum - target? A dictionary answers it in constant time, and one pass finishes the job.
The dictionary maps a prefix sum to the index where a subarray leaving that prefix out would start, which is one past the prefix's last element.
Step by step
- Create the dictionary.
indexOfValueis aDictionary<int, int>. Lookups take constant time on average, which keeps the whole method linear. - Seed it with the empty prefix. The empty prefix has sum 0 and a subarray that skips it starts at index 0, so
indexOfValue[0] = 0. Without this entry, a subarray beginning at index 0 could never be found. - Keep a running sum, starting at 0.
- Loop over every index
i, treating it as the last index of the subarray. - Update the sum with
nums[i]. - Compute the sum you need to have seen.
diffissum - target. - Look it up. If
indexOfValuecontainsdiff, an earlier prefix has exactly the right sum. - Return the pair. The stored value is the subarray's start and
iis its end. - Otherwise, record this prefix with
indexOfValue[sum] = i + 1. This happens after the lookup on purpose. - If the loop ends, nothing matched, so return
[-1, -1].
On the example, the prefix sums are 1, 2, 7, 9, 10, 13 and then 23 at index 6. At index 6, diff = 23 - 21 = 2. The sum 2 was stored at index 1 with the value 2, so the method returns [2, 6].
The solution in C#
class Solution {
public int[] SubarraySum(int[] nums, int target) {
Dictionary<int, int> indexOfValue = new Dictionary<int, int>();
indexOfValue[0] = 0;
int sum = 0;
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
int diff = sum - target;
if (indexOfValue.ContainsKey(diff)) {
return new int[] {indexOfValue[diff], i};
}
indexOfValue[sum] = i + 1;
}
return new int[] {-1, -1};
}
}
C# details worth noticing
- The indexer adds or overwrites.
indexOfValue[sum] = i + 1inserts the key if it's new and replaces the value if it exists. CallingAddwith a key that is already present throws anArgumentException, and prefix sums repeat whenever a stretch of the array adds up to zero. - Reading a missing key throws.
indexOfValue[diff]raises aKeyNotFoundExceptionwhendiffisn't a key, which is why the code guards the read withContainsKey.TryGetValuedoes the check and the read in one lookup instead of two. Dictionarylives inSystem.Collections.Generic, which is the namespace to import when you use it in your own projects.
Complexity
Time: O(n). The loop runs once, and each dictionary operation takes constant time on average.
Space: O(n). In the worst case every prefix sum is different, so the dictionary holds n + 1 entries.
Edge cases and common mistakes
- Subarray starting at index 0. This is the reason for
indexOfValue[0] = 0. For[4, -1, 2]and a target of 4, the first prefix sum is 4,diffis 0, and the seed entry gives[0, 0]. - Order of lookup and store. The lookup comes first. With a target of 0, storing the current prefix first would make
diffmatch the entry just written, and the method would report an empty subarray. With the correct order,[1, 2, 3]and target 0 returns[-1, -1], while[3, -3, 5]returns[0, 1]. - Repeated prefix sums. If the same prefix sum shows up again, its entry is overwritten with the later start. That is fine, since any valid subarray is accepted.
- No match. The method returns
[-1, -1], as in[1, 1, 5, 2, 1, 3, 10, 2, 1]with a target of 100. - Using a sliding window. Two pointers work only when all numbers are positive. This problem allows negatives.
Testing
[1, 1, 5, 2, 1, 3, 10, 2, 1]with target 21 returns[2, 6].[4, -1, 2]with target 4 returns[0, 0].[1, 2, 3]with target 2 returns[1, 1].[1, -1]with target 0 returns[0, 1].