Problem overview
The method subarraySum receives an array nums of integers, which may be positive or negative, and a number 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 target = 21, the subarray at indices 2 to 6 is [5, 2, 1, 3, 10], and 5 + 2 + 1 + 3 + 10 = 21. The answer is [2, 6].
The statement asks for O(n) time and allows O(n) extra space. Because negative numbers are allowed, a growing and shrinking window can't work, so the solution trades memory for speed with a lookup table.
Approach: remember every prefix sum
Let the prefix sum at some point be the sum of all elements before it. The sum of the subarray from index a to index i equals the prefix sum after i minus the prefix sum before a. So a subarray ending at i sums to target exactly when
prefix after i - prefix before a = target
which can be rearranged to prefix before a = prefix after i - target. While scanning left to right, we know the current prefix sum, so we know which earlier prefix sum we are looking for. If we stored every earlier prefix sum in a lookup table, together with the index where the subarray would start, the question "is there such a start?" costs one lookup.
On the example, the prefix sums after each element are 1, 2, 7, 9, 10, 13, 23. At index 6 the sum is 23, and 23 - 21 = 2. The prefix sum 2 was reached after index 1, so the subarray starts at index 2. That gives [2, 6].
Step by step
- Create the lookup table.
indexOfValueis aconstobject used as a map, typed{ [key: number]: number }: number keys and number values. For each prefix sum it will hold the index where a subarray that leaves that prefix out would start. A lookup takes constant time on average.constonly fixes which object the name refers to; entries can still be added. - Add the empty prefix.
indexOfValue[0] = 0: before any element the sum is 0, and a subarray that leaves nothing out starts at index 0. Without this entry, no subarray starting at index 0 could ever be found. - Keep a running sum,
sum, starting at 0. - Loop over each possible last index
i. - Add
nums[i]tosum, so it now covers indices 0 toi. - Compute the prefix we need.
diffissum - target, a freshconstin every iteration. - Look it up with the
inoperator, which checks whether the object has that key. - On a hit, return
[indexOfValue[diff], i]: the stored start and the current end. - Otherwise record the current prefix:
indexOfValue[sum] = i + 1. The next index is where a subarray that leaves out everything up toiwould start. Do this after the check. If it came first andtargetwere 0,diffwould equalsumand match the entry just added, which stands for an empty subarray. - Return
[-1, -1]if the loop ends with no hit.
The solution in TypeScript
class Solution {
subarraySum(nums: number[], target: number): number[] {
const indexOfValue: { [key: number]: number } = {};
indexOfValue[0] = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
const diff = sum - target;
if (diff in indexOfValue) {
return [indexOfValue[diff], i];
}
indexOfValue[sum] = i + 1;
}
return [-1, -1];
}
}
Some TypeScript details:
- Object keys are strings. The index signature
[key: number]: numberlets you writeindexOfValue[sum]with a number, but at run time JavaScript converts the number to a string key. So the prefix sum -3 is stored under the key"-3", and-3 in indexOfValuefinds it, because theinoperator converts the left side the same way. - Annotations vanish. The type
{ [key: number]: number }helps the compiler check reads and writes, but it is erased in the JavaScript output. - A
Mapworks too.Map<number, number>withhas,getandsetkeeps numbers as numbers and has no inherited keys. The plain object is enough here because every key is a number. - Overwriting. If the same prefix sum shows up twice, the second
indexOfValue[sum] = i + 1replaces the first. That's fine because any valid subarray is accepted, and the later start still gives a non-empty subarray ending at a later index.
Complexity
Time: O(n). One pass over the array, with one lookup and at most one insertion per element. Each of those takes constant time on average.
Space: O(n). In the worst case, every prefix sum is different, and the table holds n + 1 entries.
Edge cases and common mistakes
- A subarray starting at index 0. For
[1, 2, 3]andtarget = 6, the answer[0, 2]comes from the starting entryindexOfValue[0] = 0. - Negative numbers. For
[4, -2, 3]andtarget = 1, the answer is[1, 2], since -2 + 3 = 1. A solution that shrinks a window when the sum gets too large would fail here. - Target 0. For
[1, -1]the answer is[0, 1]. For[0]it is[0, 0]. For[5]there's no subarray with sum 0, and the method returns[-1, -1], which is why the table is updated after the check. - No match. For
[1, 2, 3]andtarget = 7, the answer is[-1, -1]. An empty array also gives[-1, -1]. - Storing
iinstead ofi + 1. The stored value is the start of the subarray, which is one after the prefix's last element. Storingiwould include one element too many. - Testing the value, not the key. Writing
if (indexOfValue[diff])fails when the stored start is 0, because 0 is falsy. Theincheck avoids that.
Testing
[1, 1, 5, 2, 1, 3, 10, 2, 1]withtarget = 21gives[2, 6].[4, -2, 3]withtarget = 1gives[1, 2].[1, 2, 3]withtarget = 6gives[0, 2].[1, 2, 3]withtarget = 7gives[-1, -1].[1, -1]withtarget = 0gives[0, 1].