Skip to main content
Talentd

Subarray Sum Equals K - Solution & Explanation

MediumArrayHash TablePrefix Sum16 min readAsked at: Amazon, Microsoft, Apple +44
Practice this problem

Problem Statement

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

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

Approach Overview

Problem Overview: Given an integer array nums and an integer k, count how many continuous subarrays sum exactly to k. The array can contain negative numbers, so sliding window techniques do not work reliably. You need a method that checks every possible subarray sum efficiently.

Approach 1: Brute Force with Running Sum (O(n²) time, O(1) space)

Iterate over every possible starting index of a subarray. From each start position, extend the subarray to the right while maintaining a running sum. Each time the running sum equals k, increment the count. This avoids recomputing sums from scratch but still checks all O(n²) subarrays. The approach relies only on simple iteration over the array, so space usage remains constant.

This method is straightforward and useful when explaining the problem during an interview. It clearly shows how subarrays are formed and evaluated. However, it becomes slow for large inputs because every start index expands across the remaining array.

Approach 2: Prefix Sum with HashMap (O(n) time, O(n) space)

The optimal approach uses a running prefix sum combined with a frequency map. As you iterate through the array, maintain the cumulative sum up to the current index. If the current prefix sum is curr, then any earlier prefix sum equal to curr - k forms a subarray ending at the current index with sum k. Store counts of prefix sums in a hash table so each lookup runs in O(1).

Initialize the map with {0:1} to handle cases where the subarray starting at index 0 equals k. For each element, update the running sum, check how many times curr - k has appeared, and add that to the result. Then update the frequency of the current prefix sum in the map. This transforms the nested loop into a single linear pass through the array.

Recommended for interviews: Interviewers expect the prefix sum + hash map solution because it reduces the problem from O(n²) to O(n). Starting with the brute force explanation shows you understand the problem space. Moving to prefix sums demonstrates algorithmic optimization and familiarity with hash-based counting patterns that appear in many array problems.

Approach 1: Approach 1: Brute Force

This straightforward approach involves checking all possible subarrays in the given array. We calculate the sum for each subarray and check if it equals k. Although simple, it can be inefficient for large arrays due to its O(n^2) time complexity.

This C code implements a nested loop where the outer loop selects the start of the subarray and the inner loop expands it, calculating the sum. If the sum equals k, it increments the count. The time complexity is O(n^2), and the space complexity is O(1).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Using HashMap for Prefix Sums

This optimized approach uses a hashmap to store prefix sums, facilitating the identification of subarrays with the desired sum in constant time. By keeping a count of prefix sums that have been seen, we can determine how many times a specific sum - k has appeared, suggesting that a subarray ending at the current position sums to k.

This C implementation uses a hash table to track the occurrence of prefix sums, adjusted with an offset for negative indices safety, enabling identification of subarrays summing to k. The time complexity reduces to O(n), with space complexity also improving due to the hash table.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Hash Table + Prefix Sum

We define a hash table cnt to store the number of times the prefix sum of the array nums appears. Initially, we set the value of cnt[0] to 1, indicating that the prefix sum 0 appears once.

We traverse the array nums, calculate the prefix sum s, then add the value of cnt[s - k] to the answer, and increase the value of cnt[s] by 1.

After the traversal, we return the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Using HashMap for Prefix Sums

Time Complexity: O(n)
Space Complexity: O(n)

Hash Table + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Running SumO(n²)O(1)Good for understanding subarray enumeration or when constraints are very small
Prefix Sum with HashMapO(n)O(n)General case and expected interview solution for arrays with positive and negative numbers

Video Solution

Count Subarray sum Equals K | Brute - Better -Optimal • take U forward • 824,364 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Subarray Sum Equals K easy or hard?
Subarray Sum Equals K is classified as a Medium difficulty problem. The brute force solution is simple, but recognizing the prefix sum + hash map optimization requires familiarity with cumulative sum patterns and frequency counting techniques.
Subarray Sum Equals K Python/Java solution
Python and Java implementations both follow the same prefix sum + hash map logic. Maintain a running sum, check map.get(sum - k) to count valid subarrays, and update the map with the current prefix sum frequency. The algorithm runs in O(n) time regardless of language.
How to solve Subarray Sum Equals K in O(n)?
Maintain a running prefix sum while iterating through the array. Store the frequency of every prefix sum in a hash map. For each element, check if prefixSum - k exists in the map; its frequency tells how many subarrays ending at the current index sum to k. Update the map with the current prefix sum after each step.
What is the best approach for Subarray Sum Equals K?
The most efficient approach uses prefix sums with a hash map. As you scan the array, keep a running prefix sum and store how many times each sum appears. If the current sum is curr, any earlier prefix equal to curr - k forms a valid subarray. This method runs in O(n) time with O(n) extra space.
Is Subarray Sum Equals K asked at Google/Amazon/Meta?
Subarray Sum Equals K is a common interview question at companies like Amazon, Google, and Meta because it tests prefix sum reasoning and hash map usage. Variants of this pattern also appear in many array and counting problems during coding interviews.
What data structure is used in Subarray Sum Equals K?
The optimal solution uses a hash map (or dictionary) to store frequencies of prefix sums. Combined with a running prefix sum variable, this allows constant-time lookups to determine whether a previous prefix sum creates a subarray equal to k.
What is the time complexity of Subarray Sum Equals K?
The optimal solution runs in O(n) time using a prefix sum and hash map. Each element is processed once, and hash lookups occur in constant time. A brute force approach that checks all subarrays takes O(n²) time.

Ready to solve this problem?

Practice Subarray Sum Equals K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Continuous Subarray Sum

Next

Find Pivot Index