Start learning free

LESSON 215 OF 338 · PARTIAL SUMS #2

Subarray of Given Sum in Go: O(n) with Prefix Sums and a Map

Practice O(n) Read the full explanation

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

Return the start and end indices denoting this subarray. If there are multiple solutions, you can return any of them.


Example:

Input: nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], k = 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

    GO · PARTIAL SUMS #2

    Subarray Of Given Sum in Go, explained

    Problem overview

    The function subarraySum receives a slice of integers, nums, and a number target. It returns the start and end indices of a contiguous subarray whose elements add up to target, or [-1, -1] when none exists. If several subarrays qualify, any one is accepted. The numbers may be positive or negative, and the statement asks for O(n) time with O(n) extra space.

    For 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 and 10, which add up to 21, so the answer is [2 6].

    Approach: remember earlier prefix sums

    Because negatives are allowed, the usual trick of growing and shrinking a window doesn't work: adding an element can lower the sum. Prefix sums handle any signs.

    Let sum be the total of nums[0..i]. A subarray that ends at i and starts at some index s has the total sum minus the prefix sum before s. For that to equal target, an earlier prefix must have the sum sum - target. So we keep a map from each prefix sum seen so far to the index where a subarray leaving that prefix out would start. For every i, one map lookup answers the question.

    Step by step

    1. Create the map indexOfValue with make(map[int]int). Keys are prefix sums and values are start indices.
    2. Store indexOfValue[0] = 0. The empty prefix has sum 0, and a subarray that skips it starts at index 0. Without this entry, a subarray beginning at index 0 could never be found.
    3. Declare sum as 0. It is the running prefix sum.
    4. Loop over each possible end index i.
    5. Add nums[i] to sum.
    6. Compute diff as sum - target, the prefix sum that would make the subarray work.
    7. Look diff up using the two-value form v, ok := indexOfValue[diff] in the if statement. The variable ok says whether the key exists.
    8. On a hit, return []int{v, i}: the stored start index and the current end.
    9. Otherwise record the current prefix: indexOfValue[sum] = i + 1. A subarray that skips the prefix ending at i starts at i + 1. This comes after the check, so a prefix can't match itself and produce an empty subarray when target is 0.
    10. Return []int{-1, -1} if the loop finishes.

    The solution in Go

    func subarraySum(nums []int, target int) []int {
    indexOfValue := make(map[int]int)
    indexOfValue[0] = 0
    sum := 0
    for i := 0; i < len(nums); i++ {
        sum += nums[i]
        diff := sum - target
        if v, ok := indexOfValue[diff]; ok {
            return []int{v, i}
        }
        indexOfValue[sum] = i + 1
    }
    return []int{-1, -1}
}

    Go details:

    • The comma-ok form. Reading a missing key from a map gives the zero value, 0 for int, with no error. Since 0 is also a valid start index, a plain indexOfValue[diff] couldn't tell "stored 0" from "missing". v, ok := indexOfValue[diff] sets ok to true only when the key is present.
    • Scoped to the if. Variables declared in the if header, here v and ok, exist only inside that statement and its branches.
    • Maps are unordered. Iteration order is random, but this code only looks up keys, so the order never matters.
    • Overwriting. If the same prefix sum appears again, the assignment replaces the old index with the later one. Any valid subarray is accepted, so that is fine.

    Why the starting entry matters

    For nums = [5, 1, 2] and target = 5, the first prefix sum is 5 and diff is 0. The seeded entry 0 → 0 is found, and the function returns [0 0], the single element 5. Without the seed, the lookup misses, and the function would continue past the answer.

    Tracing the example

    With target = 21, the prefix sums after each element of [1, 1, 5, 2, 1, 3, 10, 2, 1] are 1, 2, 7, 9, 10, 13, 23, 25, 26. The map starts with 0 → 0 and gains 1 → 1, 2 → 2, 7 → 3, 9 → 4, 10 → 5 and 13 → 6 as the loop goes. At i = 6 the sum is 23, so diff is 2. The key 2 maps to 2, so the function returns [2 6]: the subarray starts right after the prefix whose sum was 2, at index 2. Before that, every diff was negative (the sums were all below 21) and no negative key had been stored, so each lookup missed and the loop moved on.

    Complexity

    Time: O(n). One pass, with a constant number of map operations per element, on average.

    Space: O(n). In the worst case every prefix sum is different and the map holds n + 1 entries.

    Edge cases and common mistakes

    • No answer. For [1, 2, 3] and target = 100 the function returns [-1 -1].
    • Target zero. For [4, -4, 7] the function returns [0 1], since 4 + (-4) = 0. Storing the prefix before checking would match the current prefix with itself and report an empty range.
    • Negative numbers. For [-1, -2, 3] and target = -3 the answer is [0 1]. A sliding window would fail on inputs like this.
    • Empty slice. The loop doesn't run, so the result is [-1 -1], even for target 0.
    • Which answer you get. Several subarrays can qualify. For [3, 4, -7, 1] and target 7, the function returns [0 1], the first one it reaches.

    Testing

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