Subarray Sum Frequency 2 — Problem Statement & Solution Guide

ArraysEasySubarray Sum Equals K

TimeO(n)

SpaceO(n)

Problem Description

You are provided with a sequence of integers and a specific target sum. Your task is to determine the total count of contiguous subarrays within the sequence where the arithmetic sum of the elements exactly matches the target value. A subarray is defined as a non-empty sequence of consecutive elements from the original array.

The input consists of an array of integers and a single integer representing the target sum. The output should be a single integer representing the count of such valid subarrays. Note that the array may contain negative numbers, zero, and positive numbers, which affects the cumulative sum behavior.

For example, if the array is [1, 2, 3] and the target is 3, the valid subarrays are [3] and [1, 2], resulting in a count of 2. You must efficiently compute this count, considering that brute-force approaches may be too slow for large inputs.

DSA Pattern Breakdown

"Subarray Sum Frequency 2"

easy

WHY DOES IT MATTER?

The prefix‑sum + hash map pattern is a cornerstone for many range‑query problems, enabling linear‑time solutions where naive approaches would be quadratic. It’s widely used in competitive programming, data analytics, and real‑time monitoring systems.

OPTIMIZATION CHALLENGE

The critical insight is that a subarray sum can be expressed as the difference of two prefix sums, allowing constant‑time lookups of previously seen sums instead of recomputing sums for each subarray.

REAL-WORLD CONNECTION

Imagine a distributed log system where each log entry has a size. To find the number of contiguous log segments that sum to a target size, you’d maintain a running total and a hash map of totals seen so far—exactly the same idea as in this algorithm.

When explaining this pattern, emphasize the two‑step process: compute the running sum, then query the hash map for the complementary value. This keeps the explanation concise and highlights the algorithm’s elegance.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The core of the problem is to count the number of contiguous subarrays whose sum equals a target value. A naive solution enumerates all O(n^2) subarrays, computing each sum in O(1) with prefix sums, leading to O(n^2) time and O(1) space. This becomes infeasible for large n (e.g., 10^5) because the quadratic number of subarray checks blows up.

The optimal approach leverages the prefix sum array and a hash map (or dictionary) to store frequencies of seen prefix sums. For each index i, we compute the cumulative sum up to i, call it currSum. Any subarray ending at i with sum target must satisfy currSum - prevSum = target, where prevSum is a prefix sum seen earlier. Thus, the number of valid subarrays ending at i equals the frequency of currSum - target in the map. Updating the map with currSum after processing each element yields an O(n) time, O(n) space solution. This technique is a classic example of the “prefix sum + hash map” pattern that transforms a quadratic problem into linear time.

The key insight is that subarray sums can be expressed as differences of prefix sums, turning a range query into a constant‑time lookup. By maintaining a running count of prefix sums, we avoid recomputing sums for every subarray, drastically reducing the computational burden while preserving correctness.

Interview Questions on This Problem

Q1At Google, how would you explain the difference between the brute‑force and optimal solutions for counting subarrays with a given sum, and why the optimal solution is preferred in production systems?

I would start by describing the O(n^2) brute‑force approach that checks every possible subarray, highlighting its quadratic time complexity and impracticality for large datasets. Then I’d explain the O(n) prefix‑sum + hash map solution, emphasizing its linear time, constant‑amortized lookup, and how it scales to millions of elements—critical for real‑time analytics pipelines where latency and throughput matter.

Q2In a fintech platform interview, a candidate is asked to modify the algorithm to handle negative numbers and large input ranges. What considerations should they mention?

They should note that the prefix sum technique works regardless of sign, but the hash map must handle potentially large integer keys, so using a 64‑bit integer type is essential. They should also discuss memory usage, suggesting a streaming approach or using a balanced tree if memory is constrained, and mention that the algorithm remains O(n) time but space may grow with the number of distinct prefix sums.

Q3A startup interview focuses on code readability and maintainability. How would you structure the solution in a clean, testable way?

I would encapsulate the logic in a function that accepts the array and target, returning the count. I’d use descriptive variable names (e.g., prefixSum, freqMap), add inline comments explaining the core idea, and write unit tests covering edge cases like empty array, all zeros, and large positive/negative values. This modular design facilitates debugging and future extensions.

Examples

Example 1

Input

nums = [1, 2, 3, 4, 5], target = 9

Output

Explanation: The contiguous subarrays with sum 9 are [2, 3, 4] (2+3+4=9) and [4, 5] (4+5=9). The subarray [1, 2, 3, 4, 5] sums to 15, [1, 2, 3] sums to 6, etc. Only two subarrays match the target.

Example 2

Input

nums = [-1, 2, -3, 4, -5], target = 0

Output

Explanation: The subarrays summing to 0 are [-1, 2, -3, 4, -5] (sum=0) and [2, -3, 4, -5] (sum=0). Wait, let's re-calculate: [-1, 2, -3, 4, -5] = -1+2-3+4-5 = -3. [2, -3, 4, -5] = 2-3+4-5 = -2. Let's try [1, -1, 2, -2]. Target 0. Subarrays: [1, -1], [-1, 2, -2] is 1-2=-1. [1, -1, 2, -2] = 0. So [1, -1] and [1, -1, 2, -2] and [2, -2]. Let's use a clearer example. Input: nums = [1, -1, 2, -2], target = 0. Output: 3. Explanation: Subarrays are [1, -1] (sum 0), [2, -2] (sum 0), and [1, -1, 2, -2] (sum 0).

Example 3

Input

nums = [5, 5, 5], target = 10

Output

Explanation: The subarrays are [5, 5] starting at index 0 (sum 10) and [5, 5] starting at index 1 (sum 10). The single element subarrays sum to 5, and the full array sums to 15. Thus, there are exactly 2 valid subarrays.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Optimal Approach & Strategy

Maintain a running prefix sum and a hash map of prefix sum frequencies. For each element, increment the counter by the frequency of (current sum - target) in the map, then update the map with the current sum. This runs in O(n) time and O(n) space.

Brute Force Approach

Iterate over all start indices, compute the sum of each subarray ending at each end index, and increment a counter when the sum equals the target. This takes O(n^2) time and O(1) space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums, target) {
      let prefixSum = 0;
      let frequency = {};
      let count = 0;
      for (let num of nums) {
         prefixSum += num;
         if (prefixSum === target) {
            count++;
         }
         if (frequency[prefixSum - target]) {
            count += frequency[prefixSum - target];
         }
         frequency[prefixSum] = (frequency[prefixSum] || 0) + 1;
      }
      return count;
   }

class Solution {
   public:
      int solution(vector<int>& nums, int target) {
         int prefixSum = 0;
         unordered_map<int, int> frequency;
         int count = 0;
         for (int num : nums) {
            prefixSum += num;
            if (prefixSum == target) {
               count++;
            }
            if (frequency.find(prefixSum - target) != frequency.end()) {
               count += frequency[prefixSum - target];
            }
            frequency[prefixSum] = frequency[prefixSum] + 1;
         }
         return count;
      }
   };

class Solution {
      public int solution(int[] nums, int target) {
         int prefixSum = 0;
         Map<Integer, Integer> frequency = new HashMap<>();
         int count = 0;
         for (int num : nums) {
            prefixSum += num;
            if (prefixSum == target) {
               count++;
            }
            if (frequency.containsKey(prefixSum - target)) {
               count += frequency.get(prefixSum - target);
            }
            frequency.put(prefixSum, frequency.getOrDefault(prefixSum, 0) + 1);
         }
         return count;
      }
   }

def solution(nums, target):
      prefix_sum = 0
      frequency = {}
      count = 0
      for num in nums:
         prefix_sum += num
         if prefix_sum == target:
            count += 1
         if target in frequency:
            count += frequency[target]
         frequency[prefix_sum] = frequency.get(prefix_sum, 0) + 1
      return count

function solution(nums, target) {
      let prefixSum = 0;
      let frequency = {};
      let count = 0;
      for (let num of nums) {
         prefixSum += num;
         if (prefixSum === target) {
            count++;
         }
         if (frequency[prefixSum - target]) {
            count += frequency[prefixSum - target];
         }
         frequency[prefixSum] = (frequency[prefixSum] || 0) + 1;
      }
      return count;
   }

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Subarray Sum Frequency 2 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Subarray Sum Frequency 2 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor