Subarray Sum Equals K - Practice Coding Problems

Subarray Sum Equals K - Problem

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example: In array [1,1,1] with k=2, there are 2 subarrays with sum 2: [1,1] from index 0-1 and [1,1] from index 1-2.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,1], k = 2

› Output: 2

💡 Note: There are 2 subarrays with sum 2: [1,1] from index 0-1 and [1,1] from index 1-2

Example 2 — Single Element Match

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

› Output: 2

💡 Note: Two subarrays sum to 3: [3] at index 2, and [1,2] from index 0-1

Example 3 — No Matches

$ Input: nums = [1,2,3], k = 10

› Output: 0

💡 Note: No subarray sums to 10 since maximum possible sum is 1+2+3=6

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,1] and target sum k=2

Find Subarrays

Identify all contiguous subarrays that sum to k

Count Result

Return the total count: 2

Key Takeaway

🎯 Key Insight: Use prefix sums to transform the problem into finding pairs of sums that differ by k

Asked in

F Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is using prefix sums with hash map: if prefixSum[j] - prefixSum[i] = k, then subarray from i+1 to j has sum k. Best approach is prefix sum with hash map in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n)	O(n)	Use prefix sums and hash map to find subarrays with target sum in one pass
Brute Force - Check All Subarrays	O(n²)	O(1)	Generate all possible subarrays and count those with sum equal to k

Prefix Sum with Hash Map — Algorithm Steps

Initialize hash map with {0: 1} to handle subarrays starting from index 0
For each element, update prefix sum
Check if (prefixSum - k) exists in map and add its frequency to count
Update hash map with current prefix sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Prefix Sum

Running sum from start to current position

Check Hash Map

Look for (prefixSum - k) in map

Update Count

Add frequency to count when found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 20001
#define OFFSET 10000

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    int prefixSum = 0;
    int prefixMap[MAX_SIZE] = {0};
    prefixMap[OFFSET] = 1; // Initialize with sum 0 occurring once
    
    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i];
        
        // If (prefixSum - k) exists, it means there's a subarray with sum k
        int target = prefixSum - k + OFFSET;
        if (target >= 0 && target < MAX_SIZE) {
            count += prefixMap[target];
        }
        
        // Update the frequency of current prefixSum
        int current = prefixSum + OFFSET;
        if (current >= 0 && current < MAX_SIZE) {
            prefixMap[current]++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) hash map operations

✓ Linear Growth

Space Complexity

O(n)

Hash map can store up to n different prefix sums

⚡ Linearithmic Space

67.3K Views

High Frequency

~18 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler