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 = 2should return2because the subarrays[1, 1]and[1, 1]both sum to2.nums = [1,2,3], k = 3should return2because[1, 2]and[3]sum to3.
What is the most efficient algorithm in terms of time complexity to solve this problem? Please breakdown the time and space complexity of your solution. Be sure to think of any edge cases.
Solution
Brute Force Solution
The most straightforward approach is to check every possible subarray and see if its sum equals k. We can iterate through all possible start indices and, for each start index, iterate through all possible end indices to form subarrays. The sum of each subarray is computed, and if it matches k, we increment the count.
def subarray_sum_brute_force(nums, k):
count = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
subarray_sum = 0
for l in range(i, j + 1):
subarray_sum += nums[l]
if subarray_sum == k:
count += 1
return count
Time Complexity
O(n^3) due to the three nested loops, where n is the length of the input array.
Space Complexity
O(1) as we only use a constant amount of extra space.
Optimal Solution: Using Hashmap
A more efficient approach involves using a hashmap to store the prefix sums and their frequencies. The idea is that if prefix_sum[i] - prefix_sum[j] == k, then the subarray from j+1 to i has a sum of k. We iterate through the array, maintaining the current prefix sum. For each prefix sum, we check if prefix_sum - k exists in the hashmap. If it does, it means there's a subarray ending at the current index with a sum of k. We increment our count by the frequency of prefix_sum - k in the hashmap.
def subarray_sum_optimal(nums, k):
count = 0
prefix_sums = {0: 1}
current_sum = 0
for num in nums:
current_sum += num
if current_sum - k in prefix_sums:
count += prefix_sums[current_sum - k]
if current_sum in prefix_sums:
prefix_sums[current_sum] += 1
else:
prefix_sums[current_sum] = 1
return count
Time Complexity
O(n), where n is the length of the input array, as we iterate through the array only once.
Space Complexity
O(n) in the worst case, as the hashmap prefix_sums can store up to n distinct prefix sums.
Edge Cases
- Empty Array: If the input array is empty, the function should return 0, as there are no subarrays.
- Array with one element: The array has one element, it should return 1 if k is the same as the element, or 0 otherwise
- k = 0: The prefix sum needs to be initialized to {0:1} to account for subarrays that begins at index 0, and has sum 0.
- Negative Numbers: The algorithm works correctly with negative numbers in the array and negative values of
k.
