Start learning free

LESSON 240 OF 415 · PARTIAL SUMS #2

Subarray of Given Sum in Swift: Prefix Sums and a Dictionary in O(n)

Practice O(n) Read the full explanation

Given an array of integers and a number target, find a continuous subarray whose sum is equal to target.

Return the start and end indices denoting this subarray, or -1 and -1 if there is none. If there are multiple solutions, you can return any of them.


Example:

Input: nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], target = 21
Output: [2, 6]
Explanation: 5 + 2 + 1 + 3 + 10 = 21

Notes:

1. The array can consist of positive and negative numbers.

2. Your algorithm should run in O(n) time and use O(n) extra space.


Video Solution - Live Mock Coding Interview:
STEP 1 OF 10
    Ctrl + Enter to check

    SWIFT · PARTIAL SUMS #2

    Subarray Of Given Sum in Swift, explained

    Problem overview

    The method subarraySum receives an array nums of integers, which can be positive, negative or zero, and a number target. It must find a continuous subarray whose sum equals target and return its first and last index as [start, end]. When several subarrays work, any one is accepted. When none does, it returns [-1, -1].

    In the example, nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and target = 21. The elements at indices 2 to 6 are 5, 2, 1, 3, 10, and they add up to 21, so the answer is [2, 6].

    The statement asks for O(n) time and O(n) extra space. Because the array may contain negative numbers, a sliding window cannot be used: adding an element no longer means the sum only grows. A dictionary of prefix sums works regardless of signs.

    Approach: look up the prefix that would complete the sum

    The prefix sum at index i is the sum of nums from index 0 to i. The sum of a subarray is the difference between two prefix sums: the one at its end, minus the one just before its start.

    So for a subarray that ends at i to add up to target, the prefix sum just before its start must equal sum - target, where sum is the prefix sum at i. Call that value diff. Instead of searching the earlier positions for diff, remember every prefix sum already seen in a dictionary. A dictionary lookup takes constant time, so the whole pass is linear.

    The dictionary stores, for each prefix sum, the index right after the prefix that produced it. That is exactly where a subarray that leaves the prefix out would start. Before the loop it holds one entry: the empty prefix has sum 0, and the matching subarray would start at index 0. That entry is what makes subarrays starting at the very beginning findable.

    For the example, with target = 21, the loop goes like this:

    isumdifffound in dictionary?
    01-20no
    12-19no
    27-14no
    39-12no
    410-11no
    513-8no
    6232yes, start 2

    At i = 6 the prefix sum is 23, and 23 - 21 = 2. The prefix sum 2 was recorded after index 1, so it maps to start 2. The method returns [2, 6].

    Step by step

    1. Create indexOfValue as an empty [Int: Int]() dictionary, with var because entries will be added. Its keys are prefix sums and its values are start indices.
    2. Store the empty prefix: key 0, value 0. Without it, a subarray beginning at index 0 could never be found.
    3. Create sum at 0 as a var. It is the running prefix sum.
    4. Loop over each possible end i from 0 up to but not including nums.count.
    5. Add nums[i] to sum. It now covers indices 0 to i.
    6. Compute diff as sum - target, with let. This is the earlier prefix sum that would complete the target.
    7. Look up diff with if let start = indexOfValue[diff]. A dictionary read returns an optional, and the body only runs when the key exists.
    8. On a hit, return [start, i].
    9. Otherwise record the current prefix: indexOfValue[sum] = i + 1. This happens after the check, so a prefix is never matched with itself.
    10. Return [-1, -1] if the loop ends without a hit.

    The solution in Swift

    class Solution {
    func subarraySum(_ nums: [Int], _ target: Int) -> [Int] {
        var indexOfValue = [Int: Int]()
        indexOfValue[0] = 0
        var sum = 0
        for i in 0..<nums.count {
            sum += nums[i]
            let diff = sum - target
            if let start = indexOfValue[diff] {
                return [start, i]
            }
            indexOfValue[sum] = i + 1
        }
        return [-1, -1]
    }
}

    The Swift details worth knowing:

    • Dictionary subscripts return optionals. indexOfValue[diff] has the type Int?, and it is nil when the key is missing. A missing key is not an error and does not return 0. That is why the code unwraps the value with if let.
    • if let scope. The name start exists only inside the braces of the if, where it is a plain Int.
    • Assigning through a subscript. indexOfValue[sum] = i + 1 inserts the key if it is new and replaces its value if it already exists.
    • Type annotation by initializer. [Int: Int]() creates an empty dictionary whose type is clear from the expression, so no further annotation is needed.
    • Early return inside a loop. The method ends as soon as a match is found, and the final return [-1, -1] is only reached when nothing matched.

    Complexity

    Time: O(n). The loop makes one pass. Each step does one addition, one dictionary lookup and at most one dictionary insertion, and these take constant time on average.

    Space: O(n). The dictionary can hold one entry per prefix sum, so up to n + 1 entries.

    Edge cases and common mistakes

    • A subarray at the very start. [4, 1, 2] with target = 4 returns [0, 0]. At i = 0 the prefix sum is 4, so diff is 0, and the entry for the empty prefix supplies start 0.
    • Negative numbers. [-3, 1, 2, -4] with target = -4 returns [3, 3]. A sliding window fails on inputs like this one, while the dictionary does not care about signs.
    • Zero as the target. [5, -5, 3] with target = 0 returns [0, 1]. If the current prefix were stored before the lookup, diff would match the prefix that was just stored and report an empty subarray.
    • Repeated prefix sums. When the same prefix sum appears again, its dictionary entry is replaced by the later start. That is safe: a later start gives a shorter subarray with the same sum, and any valid subarray is accepted.
    • No match. [1, 2, 3] with target = 100 returns [-1, -1], and so does [2, 3] with target = 0.
    • Storing the wrong index. The dictionary must hold i + 1, the first index after the prefix, not i. Storing i would start the subarray one element too early, at the last element of the prefix.

    Testing

    • nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], target = 21 gives [2, 6].
    • nums = [4, 1, 2], target = 3 gives [1, 2].
    • nums = [5, -5, 3], target = 0 gives [0, 1].
    • nums = [-3, 1, 2, -4], target = -4 gives [3, 3].
    • nums = [1, 2, 3], target = 100 gives [-1, -1].
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free