560. Subarray Sum Equals K - LeetCode Fastest Solution

5 days ago5 min read

Updated: 4 days ago

Hello Code Recipian! Ready for another LeetCode challenge? Today, let's tackle another LeetCode problem that uses the prefix sum pattern, 560. Subarray Sum Equals K.

This article is part of our exciting series LeetCode problem solutions—be sure to explore the other problems in the series once you’ve mastered this one!

Alright, let’s dive into today’s problem!

Problem Statement: 560. Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of subarrays in nums whose sum is equal to k.

Example 1

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

Output: 2

Example 2

Input: nums = [1, 0, 1, 2, 1, 0, 4, 1, 3], k = 4

Output: 8

Constraints

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

Solution: 560. Subarray Sum Equals K

Let's dissect the problem statement. For a given array, a subarray is a chunk in this array where all the elements are in a continuous sequence—no skipping allowed! Think of it like highlighting a part of a sentence, you cant jump over words. For example, consider the below array:

Subarrays for the given array are:

The problem statement asks us to count all such subarrays in nums whose sum is equal to k.

A straight forward approach to solve this problem is to use two nested loops to generate all subarrays for nums and count the matching subarrays with sum k. But, because of nested loops, the time complexity of this solution is O(n^2), which for sure is not an efficient solution.

Can sliding window technique be used to solve this? Usually when we see subarray problems, one approach that naturally comes to mind is the sliding window technique. A good way to evaluate if sliding window technique can be applied for a subarray problem is to analyze the problem closely. If the problem statement has loose or flexible constraints like "subarrays with sum less than k", "smallest subarray with a greater sum" etc. this is where sliding window can be a great fit.

For subarray problem with stricter constraints like the one given in this question "subarray sum equals k", sliding window pattern cannot be applied because they violate the window expansion/contraction constraints.

Consider the below example,

Diagram showing why sliding window pattern cannot be used

In sliding window technique, we update the result both in expansion and contraction phase. We keep expanding the window as long as sum<=k and contract it when sum>k. As you can see from the above diagram, for input nums =[1, 0, 1, 0, 1] and k=4, the expected output=4, but we get 3. This is because sliding window misses the last subarray, as shown in below diagram (highlighted in red):

Diagram showing missed subarray with sum k

This is exactly why the sliding window approach won’t work here—it would overlook some subarrays and result in an incorrect outcome.

Prefix Sum Approach

Consider the below input array and k=4:

Assume we are iterating through the array and we have reached the 4th index i.e. element 1. At this point in order to get subarray with sum=4, there are two possibilities [0, 1, 2, 1] and [1, 2, 1], shown by the cells highlighted in green in the below diagram:

Let's analyze how we can arrive at this result. If you observe carefully, in order to get these two subarrays, i.e. in order to get sum k=4, we need to subtract the sum of elements not part of the subarray from the sum of all elements until the current element.

Diagram showing how to determine a subarray using subtraction

A closer examination reveals that nonSubarraySum, currentSum are nothing but prefix sums for the respective indices.

Diagram showing how prefix sum can be used

Note: If you are new to prefix sum coding pattern, we recommend you go through this article on prefix sum Coding Patterns - Prefix Sum Pattern, in order to understand this solution better.

Now that we understand how to find a subarray with sum k, let’s move on to figuring out how to count all such subarrays. Referring back to the same example, at index 4, we know two subarrays with sum=4 are possible. We identified these subarrays by subtracting the prefix sums:

And if you notice at at index 4, where prefixSum[4]=5 we can get sum=4 only when subtracted prefix sum is equal to 1 i.e. prefixSum[0] == prefixSum[1] = 1. We got 2 subarrays at index 4 since we had 2 prefix sums with value equal to 1.

From the above analysis, we can deduce that the number of possible subarrays at a particular index is determined by the count of previous prefix sums that, when subtracted, result in the desired difference of k. By applying this logic to every index in nums array, we can calculate the total count of subarrays with a sum equal to k.

And final thing to consider: since we need quick access to previously seen prefix sums while iterating through the nums array, we’ll store them in a hashmap. This hashmap will also track the frequency (count) of each prefix sum, allowing us to solve the problem efficiently.

Algorithm

Here’s a quick overview of how the algorithm works and how it can be implemented:

Initialization: Initialize a hashmap seenPrefixSum to keep track of previously encountered prefix sums and their frequencies. It takes prefix sum as key and the corresponding count as value.

Add an initial entry {0:1} to the hashmap. This ensures edge cases are handled, such as when the current prefix sum equals k.

Create an integer variable currPrefixSum and set it to 0. This will store the running prefix sum as we iterate through the nums array.
Finally, initialize a variable count to store the result—the total number of subarrays with a sum equal to k.
Count subarrays with sum k: Iterate through the nums array from start to finish. In each iteration perform the following steps:
1. Add the current element to currPrefixSum to update the running prefix sum.
2. Check if currPrefixSum - k exists in the seenPrefixSum hashmap.
  1. If yes, add the frequency of currPrefixSum - k from the hashmap to count.
  2. If no, proceed to the next step.
3. Add the current currPrefixSum to the hashmap(or update its frequency if it already exists).
4. Continue iterating through the array.
Return the final result: Once the iteration through the nums array is complete, return the value of count as the final result.

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

Simulation

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Dart Solution

Racket Solution

Complexity Analysis

Time Complexity

Time complexity of this algorithm is O(n) as we have to iterate through the array once in order to find the result.

Space Complexity

Space complexity is O(n) as we store prefix sums in the seenPrefixSum hashmap, and in the worst case when all prefix sums are unique, we will end up storing n prefix sums in hashmap.

Curious to learn more on prefix sum pattern? Checkout our other articles on prefix sum pattern:

Code Recipe Limited Time Offer: For a limited time enjoy 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Hurry—offer expiring soon - Join now.