Problem overview
The method subarraySum receives an Array[Int] of non-negative numbers and an Int called target. It must find a contiguous subarray whose elements add up to target and return its first and last index as Array(start, end). If several subarrays qualify, any one is accepted. If none does, it returns Array(-1, -1).
For nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and a target of 21, the elements from index 2 to index 6 are 5, 2, 1, 3, 10, which add up to 21, so the result is [2, 6].
Approach: a window whose sum you maintain
The brute force sums every subarray, which is O(n²) with a running sum per start index. The sliding window gets O(n) time and O(1) extra space by using the fact that every number is non-negative.
Keep a window [j..i] and its total in sum. Each step adds the next number on the right. If the total now exceeds the target, the only way to lower it is to remove numbers from the left, because adding more numbers on the right can't make a non-negative total smaller. So the window shrinks from the left until the total is no longer above the target. If the total then equals the target, the window is an answer.
This reasoning breaks with negative numbers, since adding a negative value could bring an oversized sum back down. That is why the lesson restricts the input.
On the example, the window grows through 1, 1, 5, 2, 1, 3 with a total of 13. Adding 10 makes it 23, which is above 21, so the 1 at index 0 is removed (22), then the 1 at index 1 (21). The loop stops with j = 2 and i = 6, the sum equals the target, and the method returns [2, 6].
Step by step
- Declare
jandsumasvars on separate lines, both 0.jis the left end of the window andsumits total. They arevarbecause the loop changes them. - Loop over
iinnums.indices. Each pass makesnums(i)the new right end. - Add
nums(i)tosumwithsum += nums(i). - Shrink while the sum is too big. An inner
whileloop runs whilej < i && sum > target. The checkj < ikeepsnums(i)inside the window, so it never becomes empty. - Drop the left element: subtract
nums(j)fromsum. - Move
jone step right withj += 1. Scala has no++. Sincejonly increases, it moves at mostntimes over the whole run. - Check the window. After the inner loop, still inside the
for, testsum == target. On a match, returnArray(j, i). Returning at once gives the matching window that ends earliest. - Handle failure. After the
forloop, returnArray(-1, -1).
The solution in Scala
class Solution {
def subarraySum(nums: Array[Int], target: Int): Array[Int] = {
var j = 0
var sum = 0
for (i <- nums.indices) {
sum += nums(i)
while (j < i && sum > target) {
sum -= nums(j)
j += 1
}
if (sum == target) {
return Array(j, i)
}
}
return Array(-1, -1)
}
}
The Scala details worth a closer look:
returninsidefor. Afor (i <- nums.indices)loop is turned into a call that takes a function, and areturninside it leaves the whole method. Scala 3.5 accepts this but prints a warning that such non-local returns are no longer supported and suggestsscala.util.boundary. The code compiles and returns the right values.Array(j, i)builds anArray[Int]from its arguments, which is what the declared result type needs.sumas a name. It is an ordinary variable here and doesn't clash with thesummethod that collections have.Intoverflow.Intis 32 bits and overflows silently. If the numbers could add up beyond about 2.1 billion,sumwould need to be aLong.
Complexity
Time: O(n). The outer loop visits each index once. The inner loop only ever increases j, and j stays below n, so all its iterations together number at most n.
Space: O(1). The method uses two indices and a total. The returned two-element array is the output, not working storage.
Edge cases and common mistakes
- No answer.
[1, 2, 3]with target 7 returns[-1, -1]. An empty array returns[-1, -1]as well, including for target 0. - A single element.
[5]with target 5 returns[0, 0], and with target 3 it returns[-1, -1]: the guardj < ileaves the 5 in the window, but 5 is not 3. - Zeros.
[0]with target 0 returns[0, 0].[5, 0]with target 0 returns[1, 1], because the 5 is dropped as soon as the sum exceeds 0. - Several valid answers.
[3, 0, 0, 4]with target 4 returns[1, 3], although[3, 3]is also valid. The method returns the first window that ends earliest, and any valid answer is accepted. - Checking before shrinking. Comparing
sumtotargetbefore the inner loop would miss windows that only appear after dropping elements from the left. - Using
ifinstead ofwhile. One new large number may require dropping several old ones. - Dropping the guard
j < i. For an element bigger than the target, the window would shrink to nothing, withjpassingi. With target 0 the method would then report an empty range such as[i + 1, i].
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [1, 4, 20, 3, 10, 5],target = 33gives[2, 4].nums = [1, 2, 3, 4],target = 5gives[1, 2].nums = [1, 2, 3],target = 7gives[-1, -1].nums = [5, 0],target = 0gives[1, 1].
