Problem overview
The method subarraySum receives an array of non-negative integers, nums, and a number target. It must find a continuous subarray whose elements add up to target and return its first and last indices as [start, end]. If several subarrays qualify, any one is accepted. When none exists, the method returns [-1, -1].
In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and the target is 21. The elements at indices 2 through 6 are 5, 2, 1, 3 and 10, which add up to 21, so the answer is [2, 6].
The statement asks for O(n) time and O(1) extra space, so the method can't build prefix-sum tables or hash maps.
Approach: grow on the right, shrink on the left
Trying every pair of start and end indices and adding the elements takes far too long. A sliding window does it in one pass because all numbers are non-negative, and that gives the window two useful properties:
- Adding an element on the right never decreases the sum.
- Removing an element on the left never increases the sum.
So when the sum is larger than the target, the only way to bring it down is to drop elements from the left. When it is smaller, the only way to raise it is to extend the window to the right. The window never has to move backwards, which keeps the work linear.
Keep the window as nums[j...i] together with its total in sum. For each new right end i, add nums[i], then drop elements from the left while the sum is too big. If the sum now equals the target, the window is an answer.
Step by step
- Declare the left edge and the sum. One
varline declaresjandsum, both 0. Both change inside the loop. - Loop over the right edge.
for i in 0..<nums.countmakes each index in turn the last element of the window. - Add the new element.
sum += nums[i]. - Shrink while the sum is too big. The loop condition is
j < i && sum > target. The partj < ikeeps at leastnums[i]in the window, so the window never becomes empty. - Drop the leftmost element. Inside that loop, subtract
nums[j]fromsum. - Move the left edge. Do
j += 1. Swift has no++operator. - Check for a match. After the inner loop, still inside the
forloop, ifsum == target, return[j, i]. - Report failure. After the
forloop, return[-1, -1].
The solution in Swift
class Solution {
func subarraySum(_ nums: [Int], _ target: Int) -> [Int] {
var j = 0, sum = 0
for i in 0..<nums.count {
sum += nums[i]
while j < i && sum > target {
sum -= nums[j]
j += 1
}
if sum == target {
return [j, i]
}
}
return [-1, -1]
}
}
The Swift details worth a closer look:
- Several variables on one line.
var j = 0, sum = 0declares two separate variables. Each gets its type,Int, from its initial value. - Returning an array. The result type is
[Int], so[j, i]and[-1, -1]are both array literals of two numbers. - Early return from a loop. A
returninside theforloop ends the whole method at once, so the first window found is the one returned. That is the one that ends earliest. - Half-open range.
0..<nums.countstops beforenums.count. For an empty array the range is empty and the method returns[-1, -1]. - Overflow traps. Swift's
Intis 64 bits, and addition that overflows crashes the program instead of wrapping around. Sums of ordinary test inputs are far below that limit.
Complexity
Time: O(n). The index i goes through the array once. The index j only moves right and never passes i, so over the whole run the inner loop executes at most n times.
Space: O(1). The method uses the two indices and the running sum, whatever the size of the input.
Edge cases and common mistakes
- No solution.
[1, 2, 3]with target 7 returns[-1, -1]. - Empty array. The loop doesn't run, so the method returns
[-1, -1], even when the target is 0. - A single element.
[5]with target 5 returns[0, 0]. With target 0 it returns[-1, -1]. - Zeros.
[0, 5]with target 0 returns[0, 0], because the single element 0 is a valid subarray. With[4, 0, 0, 3]and target 3, the first match is[1, 3]: the zeros and the 3 together add up to 3. Several answers can be valid, and the lesson accepts any of them. - A large first element.
[10, 1]with target 1 returns[1, 1]. Ati = 1the sum is 11, so the loop drops the 10. - Using
j <= iin the shrink loop. The window could become empty and the sum 0, which would then be reported as a match for target 0. - Negative numbers. The method relies on the numbers being non-negative. With negative values, dropping an element can raise the sum, and a different technique is needed.
Testing
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1],target = 21gives[2, 6].nums = [1, 2, 3, 4],target = 5gives[1, 2].nums = [2, 3, 1, 2, 4, 3],target = 7gives[2, 4].nums = [5],target = 5gives[0, 0].nums = [1, 2, 3],target = 7gives[-1, -1].
