Subarray Sum Equals K Leetcode Problem 560 [Python Solution]

Welcome to another coding challenge! In this blog post, we’re going to tackle the Subarray Sum Equals K problem.

This is a medium difficulty problem from LeetCode, falling under the category of Arrays & Hashing.

The task at hand is to find the total number of subarrays in a given array whose sum equals a given target value, k.

Before we dive into the problem, let’s take a moment to understand what subarrays are.

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

Now, let’s address the problem at hand:

Problem Overview

You are given an array of integers, nums, and an integer, k.

Your goal is to return the total number of subarrays within nums whose sum equals k.

Essentially, you want to find all the subarrays whose elements, when summed, equal the specified target value, k.

Here’s an example to illustrate the problem:

Example 1:

Suppose we have the following input:

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

In this case, there are two subarrays within nums whose sum equals k.

The subarrays are [1, 1] and [2].

Hence, the expected output is 2.

Example 2:

Now, consider the following input:

nums = [1, 2, 3]
k = 3

In this instance, there are two subarrays whose sum equals k.

The subarrays are [1, 2] and [3].

Hence, the expected output is again 2.

Constraints:

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

Now that we’ve got a clear understanding of the problem, let’s explore how we can efficiently solve it.

Understanding the Constraints

Before we dive into the solution, it’s important to grasp the constraints.

These constraints tell us the limits within which our solution should work efficiently.

Array Length: The length of the nums array can range from 1 to 20,000, which is a significant number.

This means our solution should be efficient, as it could potentially involve a large dataset.

Array Values: The values within the nums array can range from -1000 to 1000. This is important to note because it indicates that we may have both positive and negative numbers in the array, affecting how we calculate subarray sums.
Target Value: The k value can be as low as -10,000 and as high as 10,000. This is crucial, as we need to consider cases where k is negative, zero, or positive.

Considering these constraints, it’s evident that an efficient approach is necessary.

Now, let’s explore the solution.

Subarray Sum Equals K LeetCode Problem Solution

To solve this problem efficiently, we’ll use a hashmap to keep track of the cumulative sum of elements encountered so far.

We’ll also count how many times a particular cumulative sum (prefix sum) has occurred.

This approach will allow us to determine the number of subarrays whose sum equals k.

1. Bruteforce Approach

Before we dive into the optimized solution, let’s briefly discuss the bruteforce approach, which is not efficient.

The bruteforce approach involves checking every possible subarray in the given array to see if it sums up to k.

This approach has a time complexity of O(N^2), where N is the length of the array.

Since we have an efficient solution, we won’t implement this approach, but it’s important to understand it as a starting point.

2. An Efficient Approach with Python Code

Now, let’s implement the efficient approach.

We’ll use a Python function to solve the problem.

Here’s the code:

View on GitHub ➹

def subarraySum(self, nums: List[int], k: int) -> int:
        # Initialize variables for counting, current sum, and a hashmap.

        count = 0
        curr_sum = 0
        prefix_sum = {}

        # Initialize the prefix sum 0 with a count of 1 (base case).
        prefix_sum[0] = 1

        # Iterate through the array.

        for num in nums:
            curr_sum += num
            # Check if the difference between the current   sum and k exists in prefix_sum.

            if curr_sum - k in prefix_sum:
                count += prefix_sum[curr_sum - k]

            # Update the prefix sum count or add it to the hashmap.
            prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1

        return count

This Python function efficiently finds the total number of subarrays in the nums array whose sum equals the given target value, k.

Let’s break down how it works:

We initialize three variables: count to keep track of the number of valid subarrays, curr_sum to store the cumulative sum, and prefix_sum to maintain a hashmap of prefix sums and their counts.
To handle the case where a subarray starts from the beginning of the array and sums up to k, we initialize prefix_sum[0] = 1.

This accounts for the empty subarray (base case).

We then iterate through the nums array, adding each element to curr_sum.

As we iterate, we check if the difference between the current sum and k exists in prefix_sum.

If it does, we increment the count by the count of that specific prefix sum.

We update the prefix sum count by incrementing it or adding it to the prefix_sum hashmap.
Finally, we return the count, which represents the total number of subarrays whose sum equals k.

Time and Space Complexity

Now, let’s analyze the time and space complexity of this solution:

Time Complexity: The time complexity is O(N), where N is the length of the nums array.

We iterate through the array once, and all other operations are constant time.

Space Complexity: The space complexity is O(N), as we use a hashmap to store prefix sums.

In the worst case, we might store all unique prefix sums in the hashmap.

Reasoning Behind Our Approach

Our approach is based on the concept of prefix sums and efficiently using a hashmap to keep track of them.

Here’s a breakdown of the reasoning:

We maintain a curr_sum variable to keep track of the cumulative sum of elements as we traverse the array.

This helps us compute the sum of any subarray quickly.

To efficiently check if a subarray sums up to k, we calculate the difference curr_sum - k.

If this difference exists in our prefix_sum hashmap, it means there is a subarray that sums up to k.

By counting the occurrences of this difference in the hashmap, we can determine the number of valid subarrays.

The prefix_sum hashmap is essential for optimizing this process.

It allows us to store the cumulative sum values encountered so far, along with their counts.

This enables us to look up and count subarrays efficiently.

By handling the base case of an empty subarray (prefix_sum[0] = 1), we ensure that subarrays starting from the beginning of the array are considered.

This approach is both elegant and efficient, making use of hashmap data structures to achieve a linear time complexity.

Conclusion

In this blog post, we tackled the Subarray Sum Equals K problem, a medium-difficulty problem from LeetCode.

We discussed the problem statement, understood its constraints, and explored an efficient Python solution.

Our solution leverages the concept of prefix sums and efficiently uses a hashmap to keep track of them, making it a linear time solution.

If you found this post helpful or have any questions, feel free to comment, ask questions, make suggestions, or share this content.

Learning and understanding these coding challenges is a valuable skill for any programmer, and your engagement is greatly appreciated.

Now you have the tools to solve the Subarray Sum Equals K problem and understand the reasoning behind the solution.

Happy coding!

Question Link: Subarray Sum Equals K – LeetCode

Thank you for reading!