Subarray Sum Equals K
Medium
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.
For example:
nums = [1, 1, 1], k = 2Output: 2nums = [1, 2, 3], k = 3Output: 2
Clarify these points:
- What should be returned if
numsis null or empty? - Does the solution need to work for negative numbers?
- What is the expected time and space complexity?
- What are the constraints on the size of the input?
Solution
Brute Force Solution
The most straightforward approach is to generate all possible subarrays and check if their sum equals k. This involves two nested loops. The outer loop determines the starting index of the subarray, and the inner loop extends the subarray to the right, calculating the sum.
def subarray_sum_brute_force(nums, k):
count = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
current_sum = 0
for l in range(i, j + 1):
current_sum += nums[l]
if current_sum == k:
count += 1
return count
Time Complexity
O(n^3) because of the three nested loops, where n is the length of the nums array.
Space Complexity
O(1) as it uses only a constant amount of extra space.
Optimal Solution: Using Hashmap
We can optimize this by using a hashmap to store the cumulative sum up to each index and its frequency. The idea is that if sum[0...i] - sum[0...j] == k, then sum[0...j] == sum[0...i] - k. We can iterate through the array, calculate the cumulative sum, and check if sum - k exists in the hashmap. If it does, it means there is a subarray with the sum equal to k. The hashmap stores the frequency of each cumulative sum, allowing us to handle cases where there are multiple subarrays with the same sum.
def subarray_sum_optimal(nums, k):
count = 0
prefix_sum = 0
sum_map = {0: 1} # Initialize with 0:1 to handle cases where prefix sum == k
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_map:
count += sum_map[prefix_sum - k]
if prefix_sum in sum_map:
sum_map[prefix_sum] += 1
else:
sum_map[prefix_sum] = 1
return count
Time Complexity
O(n), where n is the length of the nums array, as we iterate through the array once.
Space Complexity
O(n) in the worst case, as the hashmap might store all the cumulative sums if they are distinct.
Edge Cases
- Empty Array: The algorithm should handle an empty input array gracefully, returning 0.
- Array with all zeros: If the array contains only zeros, the algorithm should correctly count subarrays summing to
k=0. - Negative numbers: The algorithm should work correctly with negative numbers in the array.
- k = 0: The algorithm must be able to identify subarrays that sum to zero.
Example
nums = [1, 2, 3, 4, 5], k = 9
The prefix sums are [1, 3, 6, 10, 15]
- At index 0,
prefix_sum = 1.1 - 9 = -8. Not in map. - At index 1,
prefix_sum = 3.3 - 9 = -6. Not in map. - At index 2,
prefix_sum = 6.6 - 9 = -3. Not in map. - At index 3,
prefix_sum = 10.10 - 9 = 1.1is in map with frequency1.count += 1 - At index 4,
prefix_sum = 15.15 - 9 = 6.6is in map with frequency1.count += 1
Result: 2
