Count Subarrays with Given Sum - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an integer array arr and a target sum k, your task is to find the total number of continuous subarrays whose elements add up to exactly k.

A subarray is a sequence of elements that appears in the same order in the array and is contiguous. The same element can be included in multiple subarrays if it appears in different positions.

This problem is common in applications involving range-based queries, financial analysis, and interval sum counting.

Examples❯

Input Array Target Sum (k) Count of Subarrays Description
[1, 2, 3] 3 2 Subarrays: [1, 2], [3]
[1, 1, 1] 2 2 Subarrays: [1, 1] (at two different positions)
[3, 4, 7, 2, -3, 1, 4, 2] 7 4 Subarrays: [3,4], [7], [4, 2, 1], [1, 4, 2]
[1, -1, 0] 0 3 Subarrays: [1, -1], [0], [1, -1, 0]
[] 0 0 Empty array has no subarrays
[0, 0, 0] 0 6 All possible subarrays (of lengths 1 to 3) sum to 0
[1, 2, 3] 10 0 No subarray adds up to 10
[5] 5 1 Single element equal to k
[5] 3 0 Single element not equal to k

Solution❯

Step-by-Step Solution for Beginners: Count Subarrays with Sum = k

1. Understand the Problem First

We are given an array of integers and a target number k. We are asked to count how many continuous subarrays have a sum equal to k.

Let’s take an example to better understand this: 

Input: nums = [1, 2, 3], k = 3  
Output: 2

Explanation: The subarrays [1, 2] and [3] both sum to 3.

2. Strategy: Prefix Sum + Hash Map

Instead of checking every possible subarray (which takes O(n²) time), we will use a smarter approach using:

  • Prefix Sum: Keep track of running total as we move through the array.
  • Hash Map: Store how many times each prefix sum has occurred.

3. How It Works Step by Step

Let’s say we’re at index i and the sum of elements from the beginning up to this point is prefixSum. We are looking for how many previous prefix sums satisfy: 

prefixSum - k = previousPrefixSum

If such a previousPrefixSum was seen earlier, then a subarray ending at index i has a total sum of k. We can count all such prefix sums using the hash map.

4. Solve the Given Example

Input: nums = [1, 2, 3], k = 3
Let’s walk through it: 


Initialize:
prefixSum = 0
count = 0
map = {0: 1}  (to handle subarrays starting from index 0)

Loop through the array:
- num = 1 → prefixSum = 1  
  → prefixSum - k = -2 → not in map  
  → add 1 to map → map = {0:1, 1:1}

- num = 2 → prefixSum = 3  
  → prefixSum - k = 0 → found in map!  
  → count += 1 (map[0]) → count = 1  
  → add 3 to map → map = {0:1, 1:1, 3:1}

- num = 3 → prefixSum = 6  
  → prefixSum - k = 3 → found in map!  
  → count += 1 (map[3]) → count = 2  
  → add 6 to map → map = {0:1, 1:1, 3:1, 6:1}

Final answer = 2

5. Edge Cases

  • Empty Array: No elements means no subarrays. Output = 0.
  • Negative Numbers: The prefix sum method works even if elements are negative.
  • Zeros: In cases like [0, 0, 0] and k = 0, every subarray sums to 0. We count all valid ones.
  • Multiple Matches: If a prefix sum appears multiple times, all such matches should be added to the count.

6. Why This Approach Works Efficiently

Instead of checking every pair of start and end points for subarrays, we maintain a running prefix sum and look up how many times prefixSum - k has occurred before. This lookup is done in constant time using a hash map.

This brings down the time complexity from O(n²) to O(n), which is very efficient even for large arrays.

Algorithm Steps❯

  1. Given an array arr and a target k.
  2. Initialize a prefix sum curr_sum = 0 and a hash map prefix_count to store frequency of prefix sums.
  3. Initialize count = 0.
  4. Iterate through the array:
  5. → Add current element to curr_sum.
  6. → If curr_sum == k, increment count by 1.
  7. → If curr_sum - k exists in prefix_count, add its frequency to count.
  8. → Update the frequency of curr_sum in prefix_count.
  9. Return the total count.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

int countSubarraysWithSum(int* arr, int n, int k) {
    int* prefixCount = calloc(10000, sizeof(int)); // simplistic large array
    int currSum = 0, count = 0;
    for (int i = 0; i < n; i++) {
        currSum += arr[i];
        if (currSum == k) count++;
        if (prefixCount[currSum - k + 5000]) count += prefixCount[currSum - k + 5000];
        prefixCount[currSum + 5000]++;
    }
    free(prefixCount);
    return count;
}

int main() {
    int arr[] = {1, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    printf("Count of Subarrays: %d\n", countSubarraysWithSum(arr, n, k));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Each element is visited exactly once, and all operations (hashmap lookups and updates) take constant time.
Average CaseO(n)On average, the algorithm maintains a prefix sum hashmap and performs constant-time operations per element.
Worst CaseO(n)Even in the worst case, the array is traversed only once and hashmap operations remain O(1), resulting in linear time complexity.

Space Complexity❯

O(n)

Explanation: A hashmap is used to store the frequency of prefix sums, which can grow up to the size of the input array in the worst case.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...