Problem overview
The function subarraySum receives an IntArray called nums and a number target. It must find a contiguous subarray whose sum equals target and return its first and last index as a two-element IntArray. If several subarrays qualify, any one of them is accepted. The array can hold positive and negative numbers. When no subarray adds up to target, the function returns [-1, -1].
In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and the target is 21. The subarray at indices 2 to 6 is [5, 2, 1, 3, 10], and 5 + 2 + 1 + 3 + 10 = 21, so the answer is [2, 6].
The statement asks for O(n) time and O(n) extra space. The extra space is a hash map.
Approach: remember every prefix sum
Checking every start and end takes O(n²) time. A sliding window that grows and shrinks would be linear, but it relies on every number being positive, so that adding an element only increases the sum. Negative numbers break that rule, and the window idea can't be used here.
Prefix sums work for any numbers. Let the prefix sum at some position be the sum of everything before it. The sum of a subarray is the prefix sum at its end minus the prefix sum at its start. So a subarray that ends at index i and sums to target exists exactly when an earlier prefix sum equals
sum - target
where sum is the total of all elements up to i. A hash map gives constant-time answers to the question "did I see this prefix sum before?". For each prefix sum, the map stores where the subarray that leaves that prefix out would begin: the index right after the prefix.
Here is the example. The map starts as {0: 0}. At index 0 the sum is 1, and 1 - 21 = -20 isn't in the map, so the entry 1: 1 is added. At index 1 the sum is 2, and the map gets 2: 2. The sums at indices 2 to 5 are 7, 9, 10 and 13, each stored with its index plus one. At index 6 the sum is 23, and 23 - 21 = 2 is in the map with the value 2. The answer is [2, 6].
Step by step
- Create the map. Declare
val indexOfValueas an emptyHashMap<Int, Int>(). Its keys are prefix sums and its values are the start indices of subarrays that follow them. Avalis enough, because entries can be added to a map that avalrefers to. - Store the empty prefix. Set
indexOfValue[0]to 0. The sum before the first element is 0, and a subarray that follows it starts at index 0. Without this entry no subarray starting at index 0 could be found. - Declare
sumwithvar, starting at 0. It is the running total. - Loop
iovernums.indices. Eachiis a possible last index. - Add
nums[i]tosum. It now covers the elements from index 0 toi. - Compute
diffassum - target, withval. This is the earlier prefix sum that would leave exactlytargetfor the subarray ending ati. - Look it up with
indexOfValue.containsKey(diff). - On a hit, return the answer. The subarray runs from the stored start,
indexOfValue[diff]!!, toi. - Otherwise record the current prefix. Set
indexOfValue[sum]toi + 1, where a subarray that follows this prefix begins. - If the loop ends, no subarray matched. Return
intArrayOf(-1, -1).
The solution in Kotlin
class Solution {
fun subarraySum(nums: IntArray, target: Int): IntArray {
val indexOfValue = HashMap<Int, Int>()
indexOfValue[0] = 0
var sum = 0
for (i in nums.indices) {
sum += nums[i]
val diff = sum - target
if (indexOfValue.containsKey(diff)) {
return intArrayOf(indexOfValue[diff]!!, i)
}
indexOfValue[sum] = i + 1
}
return intArrayOf(-1, -1)
}
}
The Kotlin details worth a closer look:
- Index assignment on a map.
indexOfValue[0] = 0calls the map'ssetoperator, which puts or replaces an entry. Reading withindexOfValue[diff]callsget. - Why
!!.getreturnsInt?, because a missing key givesnull.intArrayOfneeds plainInts, so!!asserts that the value isn't null. That is safe, sincecontainsKeyhas just confirmed the key. Without the assertion the code wouldn't compile. - Boxing. A
HashMap<Int, Int>stores boxed integers, so each lookup and insertion has some overhead compared with an array. It is still constant time on average. - Overwriting. If the same prefix sum shows up twice, the second assignment replaces the first, so the map keeps the later start. Any valid subarray is accepted, so this is fine, and the map never grows beyond
n + 1entries. Intarithmetic.sumandsum - targetare 32-bit values and wrap on overflow. For very large inputs,Longwould be needed.
Complexity
Time: O(n) on average. The loop runs once per element, and each iteration does one lookup and at most one insertion. Both are constant time on average for a hash map.
Space: O(n). The map holds one entry per distinct prefix sum, at most n + 1.
Edge cases and common mistakes
- A subarray starting at index 0. The seed entry
0 to 0is what finds it. For[5]with target 5, the sum is 5,diffis 0, and the function returns[0, 0]. - No match.
[1, 2, 3]with target 7 returns[-1, -1]. - An empty array. The loop never runs and the function returns
[-1, -1]. - Negative numbers.
[4, -4, 1]with target 0 returns[0, 1]: the first two numbers cancel. A window-based solution would miss cases like this. - Target 0 and the order of operations. The lookup comes before the insertion. If the current prefix were stored first,
diffwould equal the currentsumwhentargetis 0, and the code would find itself and report an empty subarray. - Several answers.
[2, -2, 2, -2]with target 2 returns[0, 0], but[2, 2]and[0, 2]are valid too. The code returns the first one it meets while scanning. - Storing
iinstead ofi + 1. The stored value is a start index. Storingiwould make every answer begin one element too early.
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [1, 2, 3],target = 7gives[-1, -1].nums = [4, -4, 1],target = 0gives[0, 1].nums = [5],target = 5gives[0, 0].