grid47 Exploring patterns and algorithms
Sep 12, 2024
5 min read
Solution to LeetCode 560: Subarray Sum Equals K Problem
Given an array nums of integers and an integer k, find the total number of contiguous subarrays whose sum equals k.
Problem
Approach
Steps
Complexity
Input: The input consists of an array nums containing integers and an integer k.
Example: Input: nums = [2, 1, 3, 4, 1], k = 4
Constraints:
• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7
Output: The output should be a single integer representing the number of subarrays whose sum equals k.
Example: Output: 3
Constraints:
• The result should be an integer representing the count of subarrays.
Goal: To find all subarrays whose sum equals k, we can maintain a running sum and use a hash map to track how many times each sum has occurred.
Steps:
• Initialize a hash map to store the frequency of sums and a variable to store the result.
• Iterate through the array, updating the running sum.
• Check if the difference between the current running sum and k exists in the hash map. If it does, increment the result by the frequency of that sum.
• Update the hash map to reflect the new sum after processing each element.
Goal: The constraints ensure that the array can have up to 20,000 elements and that the values in the array can be both positive and negative.
Steps:
• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7
Assumptions:
• The input array is non-empty.
• The integer k is within the specified range.
• Input: Input: nums = [2, 1, 3, 4, 1], k = 4
• Explanation: The subarrays that sum to 4 are [2, 1, 3], [4], and [1, 3]. Therefore, the result is 3.
• Input: Input: nums = [1, -1, 2, 3, -2], k = 3
• Explanation: The subarrays that sum to 3 are [3] and [1, -1, 2, 3]. Hence, the result is 2.
Approach: This problem can be solved efficiently using a prefix sum and a hash map to track the frequency of sums encountered during the iteration.
Observations:
• The sum of any subarray can be represented as a difference between two prefix sums.
• By keeping track of prefix sums using a hash map, we can determine how many times the sum equals k without iterating over all possible subarrays.
Steps:
• Initialize a variable to store the result (subarray count).
• Use a hash map to keep track of the number of times each prefix sum occurs.
• Iterate over the array, maintaining a running sum.
• For each element, check if the difference between the running sum and k is already in the hash map.
• If found, add the frequency of that sum to the result.
• Finally, update the hash map with the current running sum.
Empty Inputs:
• The input array will never be empty as per the problem constraints.
Large Inputs:
• The solution should efficiently handle input sizes up to 20,000 elements.
Special Values:
• If k is 0, the solution should handle subarrays that sum to zero.
Constraints:
• The solution should work efficiently even when k is a large or small value within the allowed range.
intsubarraySum(vector<int>& nums, int k) {
int res =0;
unordered_map<int, int> mp;
mp[0] =1;
int sum =0, cnt =0;
for(int i =0; i < nums.size(); i++) {
sum += nums[i];
if(mp.count(sum - k)) cnt += mp[sum - k];
mp[sum] +=1;
}
return cnt;
}
1 : Function Definition
intsubarraySum(vector<int>& nums, int k) {
Defines the function `subarraySum` which takes a vector of integers `nums` and an integer `k`, and returns the number of subarrays whose sum equals `k`.
2 : Result Initialization
int res =0;
Initializes the result variable `res` to store the count of subarrays that sum to `k`.
3 : Hash Map Initialization
unordered_map<int, int> mp;
Declares an unordered map `mp` to store prefix sums of the array. The key is the sum, and the value is its frequency of occurrence.
4 : Initialize Prefix Sum
mp[0] =1;
Initializes the hash map with the base case, where a prefix sum of `0` occurs once (for the case of an exact match of `k` from the start of the array).
5 : Prefix Sum Initialization
int sum =0, cnt =0;
Initializes `sum` to keep track of the running prefix sum and `cnt` to count the number of valid subarrays.
6 : Iterate Through Array
for(int i =0; i < nums.size(); i++) {
Begins a loop to iterate through the array `nums` to calculate prefix sums.
7 : Prefix Sum Update
sum += nums[i];
Adds the current element `nums[i]` to the running `sum`.
8 : Check for Subarray Sum
if(mp.count(sum - k)) cnt += mp[sum - k];
Checks if the prefix sum `sum - k` exists in the hash map. If it does, it means a subarray with sum `k` is found, so it adds the count of occurrences of `sum - k` to `cnt`.
9 : Update Hash Map
mp[sum] +=1;
Increments the frequency of the current prefix sum `sum` in the hash map `mp`.
10 : Return Result
return cnt;
Returns the total count of subarrays that sum to `k`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear in the size of the input array.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the prefix sums in the hash map.
