Sequential Sum Frequency — Problem Statement & Solution Guide

ArraysEasySubarray Sum Equals K

TimeO(n)

SpaceO(n)

Problem Description

Given an integer array nums and an integer k, determine how many contiguous subarrays of nums have a sum exactly equal to k. The input consists of two lines: the first line contains two space‑separated integers n (the length of the array) and k (the target sum); the second line contains n space‑separated integers representing the elements of nums. Output a single integer – the count of subarrays whose elements add up to k. The solution must run in linear time relative to n and use only O(n) additional memory.

DSA Pattern Breakdown

"Sequential Sum Frequency"

easy

WHY DOES IT MATTER?

Counting sub‑arrays with a target sum is a foundational pattern for many sliding‑window and prefix‑sum problems. Mastering it equips engineers to solve a wide range of frequency‑based queries in linear time, which is crucial for performance‑critical services.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the sum of a sub‑array can be expressed as the difference of two prefix sums. By storing frequencies of each prefix sum, you turn a nested loop into a single pass with O(1) look‑ups.

REAL-WORLD CONNECTION

Think of a streaming analytics pipeline where you need to detect when the cumulative transaction amount over any contiguous time window hits a risk threshold. The prefix‑sum + hashmap approach lets you flag such windows in real time without re‑scanning past data.

During an interview, compute the running sum on the fly, update the hashmap *after* checking the current prefix against (prefix - k). This order ensures you count sub‑arrays ending at the current index correctly and avoids off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem asks for the number of contiguous sub‑arrays whose elements sum to exactly k. A naïve solution enumerates every possible start index i and end index j, computes the sum of nums[i..j] and checks against k. This double loop yields O(n^2) time, which quickly becomes infeasible for n up to 10^5 or larger because the number of sub‑arrays grows quadratically. The optimal solution relies on prefix sums combined with a hash map (or unordered_map) that records how many times each cumulative sum has occurred while scanning the array once. For any position r, let prefix[r] be the sum of the first r elements. A sub‑array (l, r] has sum k iff prefix[r] - prefix[l] = k, i.e., prefix[l] = prefix[r] - k. By counting, for each prefix[r], how many earlier prefixes equal prefix[r] - k, we can accumulate the answer in O(n) time. This technique is a classic example of the "subarray sum equals K" pattern, which transforms a quadratic search into a linear pass using constant‑time look‑ups.

Interview Questions on This Problem

Q1How would you modify the solution if the array could contain up to 10^6 elements and the answer might exceed 32‑bit integer range?

Use a 64‑bit integer (long long) for the answer accumulator and for prefix sums. The hash map keys remain 64‑bit as well. The algorithmic complexity stays O(n) and memory O(n) for the map.

Q2Can you adapt the algorithm to count sub‑arrays with sum *at most* k instead of exactly k?

Yes. Maintain a balanced binary search tree (e.g., multiset) of prefix sums seen so far; for each prefix[r] we need the count of prefix[l] >= prefix[r] - k, which can be obtained via order‑statistics or Fenwick tree after coordinate compression, yielding O(n log n) time.

Q3Why does the hash‑map based solution work even when the array contains negative numbers?

Because the prefix sum relationship prefix[r] - prefix[l] = k holds regardless of sign. The map simply records how many times each exact cumulative value appears; negative numbers only affect the numeric values, not the correctness of the equality check.

Examples

Example 1

Input

5 5
1 2 3 2 1

Output

Explanation: All contiguous subarrays are examined. The subarrays [2,3] (indices 1‑2) and [3,2] (indices 2‑3) each sum to 5. No other subarray reaches the target, so the answer is 2.

Example 2

Input

6 0
0 0 0 0 0 0

Output

Explanation: Every possible subarray of a zero‑filled array sums to 0. With n = 6, the number of subarrays is n·(n+1)/2 = 6·7/2 = 21.

Example 3

Input

7 4
3 -1 2 1 -2 4 0

Output

Explanation: The subarrays whose sums equal 4 are: 1. indices 0‑2 → 3 + (-1) + 2 = 4 2. indices 1‑5 → -1 + 2 + 1 + (-2) + 4 = 4 3. indices 5‑5 → 4 = 4 4. indices 5‑6 → 4 + 0 = 4 5. indices 1‑6 → -1 + 2 + 1 + (-2) + 4 + 0 = 4 Thus, five distinct contiguous subarrays meet the requirement.

Constraints

1 <= n <= 2*10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= k <= 10^9
The algorithm should run in O(n) time and O(n) auxiliary space.

Optimal Approach & Strategy

Maintain a hash map of prefix‑sum frequencies while scanning once; for each prefix, add the count of (prefix‑k) seen so far to the answer. This runs in O(n) time with O(n) auxiliary space.

Brute Force Approach

Enumerate all start and end indices, compute each sub‑array sum, and compare to k. This requires O(n^2) time and O(1) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums, targetSum) {
   let count = 0;
   for (let i = 0; i < nums.length; i++) {
       let currentSum = 0;
       for (let j = i; j < nums.length; j++) {
           currentSum += nums[j];
           if (currentSum === targetSum) {
               count++;
           }
       }
   }
   return count;
}

class Solution {
   public:
       int solution(vector<int>& nums, int targetSum) {
           int count = 0;
           for (int i = 0; i < nums.size(); i++) {
               int currentSum = 0;
               for (int j = i; j < nums.size(); j++) {
                   currentSum += nums[j];
                   if (currentSum == targetSum) {
                       count++;
                   }
               }
           }
           return count;
       }
   };

class Solution {
   public int solution(int[] nums, int targetSum) {
       int count = 0;
       for (int i = 0; i < nums.length; i++) {
           int currentSum = 0;
           for (int j = i; j < nums.length; j++) {
               currentSum += nums[j];
               if (currentSum == targetSum) {
                   count++;
               }
           }
       }
       return count;
   }
}

def solution(nums, targetSum):
   count = 0
   for i in range(len(nums)):
       currentSum = 0
       for j in range(i, len(nums)):
           currentSum += nums[j]
           if currentSum == targetSum:
               count += 1
   return count

function solution(nums, targetSum) {
   let count = 0;
   for (let i = 0; i < nums.length; i++) {
       let currentSum = 0;
       for (let j = i; j < nums.length; j++) {
           currentSum += nums[j];
           if (currentSum === targetSum) {
               count++;
           }
       }
   }
   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.

Sequential Sum Frequency Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Sequential Sum Frequency — 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