Start learning free

LESSON 239 OF 414 · PARTIAL SUMS #2

Subarray of Given Sum in Scala: Prefix Sums and a HashMap 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

    SCALA · PARTIAL SUMS #2

    Subarray Of Given Sum in Scala, explained

    Problem overview

    The method subarraySum receives an Array[Int] called nums and an integer target. The numbers can be positive, negative or zero. The method must find a continuous subarray whose sum equals target and return its start and end indices. If several subarrays qualify, any one of them is accepted. When none exists, it returns [-1, -1].

    For nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and target = 21, the answer is [2, 6], because 5 + 2 + 1 + 3 + 10 = 21.

    The statement asks for O(n) time and O(n) extra space. Since negative numbers are allowed, a two-pointer window doesn't work here: adding an element no longer always increases the sum. Prefix sums with a map do.

    Approach: look up the prefix that must have come earlier

    Let sum be the prefix sum at index i, the sum of all elements from index 0 to i. A subarray that ends at i and starts at some index s has the sum sum - (the prefix sum just before s). For that to equal target, the earlier prefix sum has to be sum - target.

    So at every index the question becomes: has a prefix with the sum sum - target already appeared? A map answers it in constant time. Its keys are the prefix sums seen so far, and each value is the index where the subarray that leaves that prefix out would start, which is one past the prefix's last index.

    On the example the prefix sums are 1, 2, 7, 9, 10, 13, 23, 25, 26. At index 6 the prefix sum is 23 and 23 - 21 = 2. The prefix sum 2 was recorded after index 1, so the map holds the start index 2. The answer is [2, 6].

    Step by step

    1. Create indexOfValue as a val holding a mutable HashMap[Int, Int]. Scala's default Map is immutable, so the code names the mutable class by its full path, scala.collection.mutable.HashMap. The map stays the same object, and only its contents change, which is why val is enough.
    2. Store the key 0 with the value 0: indexOfValue(0) = 0. The empty prefix has sum 0, and a subarray that leaves it out starts at index 0. Without this entry, no subarray starting at index 0 could ever be found.
    3. Declare sum as a var equal to 0. It is the running prefix sum.
    4. Loop i over nums.indices. Each index is a possible last index of the subarray.
    5. Add nums(i) to sum.
    6. Compute diff = sum - target as a val. It is the prefix sum we hope to find in the map.
    7. Check indexOfValue.contains(diff).
    8. On a hit, return Array(indexOfValue(diff), i). The stored value is the start of the subarray, and i is the end.
    9. Otherwise record the current prefix: indexOfValue(sum) = i + 1. A subarray that leaves out the prefix ending at i starts at i + 1.
    10. If the loop ends, no subarray matched, so return Array(-1, -1).

    The order of the check and the store matters. With target = 0, storing first would let diff match the entry for the current prefix, and the method would report an empty subarray.

    The solution in Scala

    class Solution {
    def subarraySum(nums: Array[Int], target: Int): Array[Int] = {
        val indexOfValue = scala.collection.mutable.HashMap[Int, Int]()
        indexOfValue(0) = 0
        var sum = 0
        for (i <- nums.indices) {
            sum += nums(i)
            val diff = sum - target
            if (indexOfValue.contains(diff)) {
                return Array(indexOfValue(diff), i)
            }
            indexOfValue(sum) = i + 1
        }
        return Array(-1, -1)
    }
}

    The Scala details worth knowing:

    • Map update and lookup both use parentheses. indexOfValue(0) = 0 puts a value in the map, and indexOfValue(diff) reads one. Reading a key that isn't in the map throws a NoSuchElementException ("key not found"), which is why the code calls contains first. The alternative is get(diff), which returns an Option, and getOrElse(diff, -1), which gives a default value.
    • Writing an existing key replaces its value. When the same prefix sum appears twice, the later start index overwrites the earlier one. Any valid subarray is accepted, so this is fine.
    • return inside a for. The loop body is passed to foreach as a function, and a return there leaves the whole method. Scala 3.5 still compiles this, but warns that returns from inside a function body are no longer supported and suggests scala.util.boundary and boundary.break instead. The warning doesn't stop the program from running. The same method written with boundary and break(Array(indexOfValue(diff), i)) returns the same results.
    • Int overflow. The prefix sums are 32-bit Ints, so very large inputs could wrap around silently. Switching sum and the map keys to Long avoids this.

    Complexity

    Time: O(n) on average. The loop runs once per element, and each hash map operation takes constant time on average.

    Space: O(n). The map holds up to n + 1 prefix sums.

    Edge cases and common mistakes

    • No matching subarray. [1, 2, 3] with target = 100 returns [-1, -1].
    • A subarray from index 0. [3, -1, 2] with target = 3 returns [0, 0]. The entry for the empty prefix makes it findable. [2, 3] with target = 5 relies on the same entry to return [0, 1].
    • Negative numbers. [-5, 5, 1] with target = 1 returns [2, 2]. The prefix sums are -5, 0, 1. The prefix 0 was last stored with start index 2, so the answer is the single element at index 2. The subarray [-5, 5, 1] from 0 to 2 also sums to 1, but the method only has to return one answer.
    • Zeros. [0, 1] with target = 0 returns [0, 0], the single zero. A target of 0 never produces an empty subarray, thanks to the check-then-store order.
    • Storing the index instead of i + 1. The answer would start one element too early and include the element at the end of the prefix.
    • Using a sliding window. It relies on all numbers being positive. With negative numbers the window can't decide whether to grow or shrink.
    • An empty array. The loop never runs and the method returns [-1, -1].

    Testing

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