Home/Questions/Q 3538
Next
In Process

RTSALL Latest Articles

Ahmedelkomy
Asked: 2026-09-11T09:53:55-05:00 In: ,

Subarray Sum Equals K: Why Two Pointers fails with negative numbers and Hash Map is mandatory

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

Many people try to use a Sliding Window / Two Pointers approach, but it fails whenever the array contains negative numbers. Why does the sliding window fail, and how does the Prefix Sum Frequency Hash Map solve it in O(N) time?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhishek
    Begginer

    Here is the C++20 implementation of Subarray Sum Equals K with negative values using std::unordered_map.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdint>

int subarraySum(const std::vector<int>& nums, int k) {
    std::unordered_map<int64_t, int> prefix_counts;
    prefix_counts[0] = 1; // Base case

    int64_t curr_sum = 0;
    int total_subarrays = 0;

    for (int x : nums) {
        curr_sum += x;
        int64_t target = curr_sum - k;

        auto it = prefix_counts.find(target);
        if (it != prefix_counts.end()) {
            total_subarrays += it->second;
        }
        prefix_counts[curr_sum]++;
    }
    return total_subarrays;
}

int main() {
    std::vector<int> nums = {1, -1, 1, 1, 1, -1};
    int k = 2;
    std::cout << "Subarrays summing to " << k << ": " << subarraySum(nums, k) << "n";
    return 0;
}

    Complexity: O(N) time and O(N) memory.

    • 0
  2. Abhay Tiwari
    Begginer

    This is a classic trap that catches even intermediate developers. Let’s see why two pointers collapse and why prefix math is the ultimate solution.

    1. Why Two Pointers Fails on Negative Numbers

    A sliding window relies on a fundamental monotonic invariant:

    • If the current sum is too small, expanding the right pointer will increase the sum.
    • If the current sum is too large, contracting the left pointer will decrease the sum.

    The moment you introduce negative numbers, this invariant is destroyed! Expanding the right pointer might add -10, making the sum smaller. Shrinking the left pointer might drop -5, making the sum larger. You can no longer make greedy left/right decisions!

    2. The Prefix Sum Invariant

    Let prefix[i] be the cumulative sum from index 0 to i.

    The sum of any contiguous subarray from index j + 1 to i is given by: sum(j+1 ... i) = prefix[i] - prefix[j].

    We want this subarray sum to equal k:

    prefix[i] - prefix[j] = k
prefix[j] = prefix[i] - k

    The Breakthrough: As you iterate through the array maintaining a running prefix sum curr_sum, you simply ask the hash map: ‘How many times have we already seen a prefix sum equal to curr_sum - k in the past?’

    Every time you find that value in the hash map, you have found a valid subarray that sums exactly to k!

    Clean Python 3.12 Implementation

    from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    """Counts subarrays summing to k in O(N) time and O(N) space."""
    # Base case: A prefix sum of 0 has occurred once (an empty prefix)
    prefix_counts: dict[int, int] = defaultdict(int)
    prefix_counts[0] = 1

    curr_sum = 0
    total_subarrays = 0

    for x in nums:
        curr_sum += x
        target = curr_sum - k
        
        # Add all occurrences of the complementary prefix sum
        if target in prefix_counts:
            total_subarrays += prefix_counts[target]
            
        # Record current prefix sum
        prefix_counts[curr_sum] += 1

    return total_subarrays

    Why prefix_counts[0] = 1 is Critical

    If you forget prefix_counts[0] = 1, any subarray that starts at index 0 and sums to k (e.g. nums = [3, ...], k = 3) will produce curr_sum = 3, and look for curr_sum - k = 0 in the map. Without the base case, it would fail to count that valid subarray!

    Complexity Breakdown

    • Time Complexity: O(N). Single pass through the array with O(1) hash map lookups.
    • Space Complexity: O(N) to store prefix sum frequencies.
    • 0