Start learning free

LESSON 242 OF 414 · PARTIAL SUMS #2

Subarray of Given Sum in Rust: O(n) with Prefix Sums and a HashMap

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

    RUST · PARTIAL SUMS #2

    Subarray Of Given Sum in Rust, explained

    Problem overview

    The function subarray_sum receives a vector of integers, nums, and a number target. It must find a contiguous run of elements whose sum equals target and return its first and last index as a two-element vector. If several runs qualify, any of them is accepted. If none does, it returns [-1, -1].

    The numbers can be negative as well as positive. 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 and 10, which add up to 21, so the answer is [2, 6].

    The budget is O(n) time and O(n) extra space.

    Approach: prefix sums and a lookup table

    The brute-force idea tries every start and every end and adds up each run, which is O(n²) with a running sum and O(n³) without one. The usual speed-up for non-negative numbers is a sliding window, but it relies on the sum growing as the window grows. With negative numbers that fails, so the lesson uses another tool.

    The prefix sum at a position is the sum of everything from index 0 up to that position. The sum of the run from index a to index i is the prefix sum at i minus the prefix sum just before a. So a run ending at i sums to target exactly when some earlier prefix sum equals sum - target, where sum is the prefix sum at i.

    That turns the search into a lookup. While scanning left to right, remember every prefix sum seen so far, together with where the run that leaves that prefix out would start. At each position, ask whether sum - target is already in the table. A HashMap answers in constant time on average, so the whole scan is linear.

    Take nums = [3, 4, -2, 5] and target = 7. The prefix sums are 3, 7, 5 and 10. At index 1 the sum is 7 and sum - target is 0. The empty prefix has sum 0 and the run would start at index 0, so the answer is [0, 1]: 3 + 4 = 7.

    Step by step

    1. Create the table as a mutable HashMap<i32, i32>. It maps a prefix sum to the index right after that prefix, which is where a run that leaves the prefix out begins. It is mut because it is modified.
    2. Insert the empty prefix: sum 0, start index 0. Without this entry, a run that begins at index 0 could never be found, because there is no earlier prefix to subtract.
    3. Declare the running sum sum as a mutable i32 starting at 0.
    4. Loop over each possible last index i in 0..nums.len().
    5. Add nums[i] to sum, so it becomes the prefix sum at i.
    6. Compute diff as sum - target: the prefix sum an earlier position would need for the run after it to total target.
    7. Look diff up. get returns an Option holding a reference, so if let Some(&start) runs the body only on a hit and copies the stored index out of the reference.
    8. On a hit, return vec![start, i as i32]. The index i is a usize, so it needs an as i32 conversion to fit the vector of i32.
    9. Otherwise record the current prefix: insert sum with the value i as i32 + 1. The as operator binds tighter than +, so i is converted first and then 1 is added.
    10. After the loop, return vec![-1, -1] with no semicolon, so it is the function's value.

    The order inside the loop matters: the lookup comes before the insert. With target = 0, inserting first would let diff match the current prefix itself and report an empty run.

    The solution in Rust

    impl Solution {
    fn subarray_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut index_of_value: HashMap<i32, i32> = HashMap::new();
        index_of_value.insert(0, 0);
        let mut sum: i32 = 0;
        for i in 0..nums.len() {
            sum += nums[i];
            let diff = sum - target;
            if let Some(&start) = index_of_value.get(&diff) {
                return vec![start, i as i32];
            }
            index_of_value.insert(sum, i as i32 + 1);
        }
        vec![-1, -1]
    }
}

    The Rust details worth a closer look:

    • get returns an Option. A missing key gives None, not a default value and not a panic. get(&diff) takes a reference to the key, and the result is an Option<&i32>.
    • The &start pattern. Inside Some(&start), the & matches the reference and binds start to the i32 behind it. Without it, start would be a &i32, and vec![start, i as i32] would not compile.
    • insert overwrites. If a prefix sum appears twice, the second insert replaces the stored start with the later one. That is harmless, since any valid run is accepted.
    • return versus the last expression. Leaving the loop early needs return. The final vec![-1, -1] has no semicolon, so it is the value the function ends with.
    • Overflow. Built with optimizations, as the lessons are, i32 arithmetic that overflows wraps silently. A debug build would panic instead. The solution assumes sums that fit in an i32.

    Complexity

    Time: O(n). The loop runs at most n times, and each pass does one addition, one subtraction, one lookup and one insertion. The hash map operations take constant time on average.

    Space: O(n). The map holds at most one entry for the empty prefix plus one per element.

    Edge cases and common mistakes

    • A run that starts at index 0. For [1, 2, 3] and target 6, the answer [0, 2] depends on the entry for the empty prefix. Forgetting it gives [-1, -1].
    • Target 0 with a zero-sum run. For [4, -4, 3] and target 0, the prefix sums are 4, 0, 3. At index 1 the sum is 0, diff is 0, and the table returns start 0, so the answer is [0, 1].
    • Target 0 with no such run. For [1, 2, 3] the function returns [-1, -1]. This is the case where inserting before the lookup would wrongly report an empty run.
    • Empty vector. The loop does not run and the function returns [-1, -1].
    • Repeated prefix sums. For [5, -2, -3, 4] and target 4, the prefix sums are 5, 3, 0, 4. The sum 0 is stored first for the empty prefix and again at index 2, where it is overwritten with start 3. At index 3 the function returns [3, 3], the single element 4. It is a valid run, though not the longest one.
    • Negative numbers. A sliding window that shrinks when the sum is too large breaks as soon as a negative number appears. The prefix-sum lookup does not care about signs.

    Testing

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