560. Subarray Sum Equals K
Problem Description
The problem at hand involves finding the total number of contiguous subarrays within a given array of integers (nums
) that add up to a specified integer (k
). A subarray is defined as a continuous, non-empty sequence of elements taken from the array.
To better understand the problem, let's consider an example:
If our input nums
is [1, 2, 1, 2, 1]
and k
is 3
, we need to find all the subarrays where the elements sum to 3
. In this case, there are several such subarrays: [1, 2]
, [2, 1]
, [1, 2]
, [1, 2, 1] - ([2, 1] after removing the last element)
, hence the output would be 4
.
Intuition
The solution approach involves using a cumulative sum and hashmap (Counter) to keep track of the number of ways a certain sum can occur up to the current point in the array. The cumulative sum (s
) represents the total sum of all elements up to the current index.
As we traverse the array, we attempt to find the number of times the complement of the current cumulative sum, given by the difference (s - k
), has already appeared. This is because if we have seen a sum s - k
before, then adding k
to this sum would give us s
, and thus, there exists a subarray ending at the current index which sums to k
.
The reason a Counter is initialized with {0: 1}
is because a cumulative sum of 0
occurs once by default before the start of the array (think of it as a dummy sum to start the process).
Given this setup, for each element in nums
:
- We calculate the current cumulative sum (
s
) by adding the current element to it. - We update the answer (
ans
) by adding the count of how many timess - k
has occurred, because each occurrence represents a potential subarray that sums tok
. - Finally, we increment the count of the current cumulative sum in our hashmap, to be used for subsequent elements.
This algorithm effectively uses the prefix sum concept along with the hashmap to check for the existence of a required sum in constant time, leading to an efficient solution with a linear time complexity, O(n).
Learn more about Prefix Sum patterns.
Solution Approach
The solution uses a hashmap (in Python, a Counter
) to keep track of the cumulative sums at each index and how many times each sum occurs. It follows these steps:
-
Initialize the
Counter
with{0: 1}
- This implies that there is one subarray ([]
) that sums up to0
before we start processing the array. -
As we iterate over the array
nums
:-
Update the running total
s
by adding the current element. This is done bys += num
. -
Determine if
s - k
has been seen before. The count ofs - k
in thecounter
tells us how many subarrays (ending right before the current index) have a sum that would complement the remainder of the current sum to reachk
. This is done byans += counter[s - k]
. -
Update the
counter
with the new cumulative sum. Increment the existing value ofcounter[s]
by1
, or set it to1
ifs
is not yet a key in the counter. This is done bycounter[s] += 1
.
-
-
After the loop ends, the value held in
ans
is the total number of contiguous subarrays that add up tok
.
The use of the running total (or cumulative sum) allows us to check for the existence of any subarray ending at the current index which sums to k
, by checking if there is a sum of s - k
earlier in the array. The Counter
is essential here as it lets us track and retrieve the number of occurrences of each sum in constant time, which keeps the overall time complexity linear, O(n).
This method is efficient both in terms of time and space. There is no need for nested loops (which would result in O(n^2) time complexity), and we only need extra space for the hash table which stores at most n
key-value pairs where n
is the number of elements in nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider the input nums = [3, 4, -1, 2, 1]
and k = 5
. We want to find all contiguous subarrays summing to k
, which is 5
in this case.
Following the solution approach step by step:
-
We initialize our
Counter
with{0: 1}
to account for the base case where a subarray can start from the beginning of the array. -
Now, we iterate over the array
nums
. We'll keep track of our cumulative sum (s
) and initializeans
to0
.- Start with the first element:
s = 3
. No previous sum ofs - k = -2
exists, so don't updateans
. Then, update the counter toCounter = {0: 1, 3: 1}
. - Move to the second element:
s = 3 + 4 = 7
. We've seens - k = 2
before? No, soans
remains the same. Update the counter toCounter = {0: 1, 3: 1, 7: 1}
. - Third element:
s = 7 - 1 = 6
. We check fors - k = 1
. It does not exist. Update the counter toCounter = {0: 1, 3: 1, 7: 1, 6: 1}
. - Fourth element:
s = 6 + 2 = 8
. Look fors - k = 3
. We have seen3
before, once. Increaseans
by1
as there is one subarray ending here that sums to5
. Update the counter toCounter = {0: 1, 3: 1, 7: 1, 6: 1, 8: 1}
. - Fifth element:
s = 8 + 1 = 9
. Check fors - k = 4
. We have not seen4
before, soans
remains1
. Update the counter toCounter = {0: 1, 3: 1, 7: 1, 6: 1, 8: 1, 9: 1}
.
- Start with the first element:
-
After iterating through all elements, our
ans
value, which is1
, represents the total number of contiguous subarrays that sum up to5
. The subarray in this example is[4, -1, 2]
.
By using a cumulative sum and a hashmap (Counter
), we accurately and efficiently found all the contiguous subarrays that add up to a given sum with a single pass through the array. This method avoids the use of nested loops for a better time complexity of O(n).
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def subarraySum(self, nums: List[int], k: int) -> int:
5 # Initialize a counter to keep track of the cumulative sums encountered
6 cumulative_sum_counter = Counter({0: 1})
7
8 # 'count_subarrays' will store the total count of subarrays that sum up to 'k'
9 count_subarrays = 0
10
11 # 'cumulative_sum' holds the sum of numbers seen so far
12 cumulative_sum = 0
13
14 # Iterate through the list of numbers
15 for num in nums:
16 # Update the cumulative sum
17 cumulative_sum += num
18
19 # If there is a previous cumulative sum such that current_sum - k
20 # is equal to that previous sum, then a subarray ending at the current
21 # position would sum to 'k'
22 count_subarrays += cumulative_sum_counter[cumulative_sum - k]
23
24 # Increase the count of the current cumulative sum by 1 in the counter
25 cumulative_sum_counter[cumulative_sum] += 1
26
27 # Return the total number of subarrays that sum up to 'k'
28 return count_subarrays
29
1class Solution {
2
3 public int subarraySum(int[] nums, int k) {
4 // Map for storing the cumulative sum and its frequency.
5 Map<Integer, Integer> sumFrequencyMap = new HashMap<>();
6
7 // Initializing with zero sum having frequency one.
8 sumFrequencyMap.put(0, 1);
9
10 int totalCount = 0; // This will hold the number of subarrays that sum to k.
11 int cumulativeSum = 0; // This holds the cumulative sum of elements.
12
13 // Loop over all elements in the array.
14 for (int num : nums) {
15 // Add the current element to the cumulative sum.
16 cumulativeSum += num;
17
18 // If cumulativeSum - k exists in map, then there are some subarrays ending with num that sum to k.
19 totalCount += sumFrequencyMap.getOrDefault(cumulativeSum - k, 0);
20
21 // Increment the frequency of the current cumulative sum in the map.
22 // If the cumulative sum isn't already in the map, DefaultValue (0) will be used first.
23 sumFrequencyMap.put(cumulativeSum, sumFrequencyMap.getOrDefault(cumulativeSum, 0) + 1);
24 }
25
26 // Return the total count of subarrays that sum to k.
27 return totalCount;
28 }
29}
30
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 // This function returns the number of subarrays that sum up to k.
8 int subarraySum(vector<int>& nums, int k) {
9 unordered_map<int, int> prefixSumFrequency;
10 prefixSumFrequency[0] = 1; // Base case: there's one way to have a sum of 0 (no elements).
11
12 int answer = 0; // Variable to store the number of subarrays that sum to k.
13 int cumulativeSum = 0; // Variable to store the cumulative sum of elements.
14
15 // Iterate through the array to calculate the cumulative sum and count subarrays.
16 for (int num : nums) {
17 cumulativeSum += num; // Update the cumulative sum.
18 // If cumulativeSum - k exists in prefixSumFrequency, then a subarray ending at current
19 // index has a sum of k. We add the count of those occurrences to answer.
20 answer += prefixSumFrequency[cumulativeSum - k];
21 // We then increment the count of cumulativeSum in our frequency map.
22 prefixSumFrequency[cumulativeSum]++;
23 }
24
25 // Return the total count of subarrays that sum up to k.
26 return answer;
27 }
28};
29
1function subarraySum(nums: number[], targetSum: number): number {
2 let totalCount = 0; // This will hold the final count of subarrays
3 let currentSum = 0; // This will store the cumulative sum of elements
4 const sumFrequency = new Map(); // This map will store the frequency of sums encountered
5
6 sumFrequency.set(0, 1); // Initialize map with a zero sum having one occurrence
7
8 // Loop through each number in the input array
9 for (const num of nums) {
10 currentSum += num; // Add current number to the cumulative sum
11
12 // If (currentSum - targetSum) is a sum we've seen before, it means there is a subarray
13 // which adds up to the targetSum. We add to totalCount the number of times we've seen this sum.
14 totalCount += sumFrequency.get(currentSum - targetSum) || 0;
15
16 // Update the frequency of the currentSum in the map.
17 // If currentSum is already present in the map, increment its count, otherwise initialize it to 1.
18 sumFrequency.set(currentSum, (sumFrequency.get(currentSum) || 0) + 1);
19 }
20
21 return totalCount; // Return the total count of subarrays which sum up to targetSum
22}
23
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
is the length of the input list nums
. This is because the code iterates through the list once, performing a constant number of operations for each element: calculating the cumulative sum s
, checking and updating the counter
, and incrementing ans
.
The space complexity of the code is also O(n)
, due to the counter
object that can potentially store an entry for each unique cumulative sum s
. In the worst case, this could be every subarray sum if all numbers in nums
are distinct and add up to different sums, creating a new key for almost each s
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.