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.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107The key challenge in #560 Subarray Sum Equals K is efficiently counting how many contiguous subarrays sum to a given value k. A naive approach checks every possible subarray using nested loops and calculates the sum each time, leading to O(n²) time complexity.
A more optimal method uses the concept of prefix sums. As you traverse the array, maintain a running cumulative sum. If the difference between the current prefix sum and k has appeared before, it means a subarray ending at the current index sums to k. To track this efficiently, store prefix sum frequencies in a hash map.
This approach allows you to update counts in constant time while scanning the array once. The prefix sum technique combined with hashing reduces the overall complexity to O(n) time with O(n) extra space, making it suitable for large inputs commonly seen in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (Check all subarrays) | O(n²) | O(1) |
| Prefix Sum + Hash Map | O(n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Will Brute force work here? Try to optimize it.
Can we optimize it by using some extra space?
What about storing sum frequencies in a hash table? Will it be useful?
sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1. Can we use this property to optimize it.
This straightforward approach involves checking all possible subarrays in the given array. We calculate the sum for each subarray and check if it equals k. Although simple, it can be inefficient for large arrays due to its O(n^2) time complexity.
Time Complexity: O(n^2)
Space Complexity: O(1)
1#include <stdio.h>
2
3int subarraySum(int* nums, int numsSize, int k) {
4 int count = 0;
5 for (int start = 0; start < numsSize; start++) {
6 int sum = 0;
7 for (int end = start; end < numsSize; end++) {
8 sum += nums[end];
9 if (sum == k) count++;
10 }
11 }
12 return count;
13}
14
15int main() {
16 int nums[] = {1, 1, 1};
17 int k = 2;
18 int size = sizeof(nums)/sizeof(nums[0]);
19 printf("%d\n", subarraySum(nums, size, k));
20 return 0;
21}
22This C code implements a nested loop where the outer loop selects the start of the subarray and the inner loop expands it, calculating the sum. If the sum equals k, it increments the count. The time complexity is O(n^2), and the space complexity is O(1).
This optimized approach uses a hashmap to store prefix sums, facilitating the identification of subarrays with the desired sum in constant time. By keeping a count of prefix sums that have been seen, we can determine how many times a specific sum - k has appeared, suggesting that a subarray ending at the current position sums to k.
Time Complexity: O(n)
Space Complexity: O(n)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to compute the sum of any subarray using the difference of two cumulative sums. When combined with a hash map to track previously seen sums, it helps detect valid subarrays quickly without recomputing sums repeatedly.
Yes, this problem is commonly asked in FAANG and other top tech company interviews. It tests understanding of prefix sums, hash maps, and efficient counting of subarrays.
The optimal approach uses a prefix sum combined with a hash map. While traversing the array, you store frequencies of prefix sums and check if the difference between the current sum and k has appeared before. This allows counting valid subarrays in O(n) time.
A hash map (or dictionary) is the most useful data structure for this problem. It stores the frequency of prefix sums so you can quickly determine whether a previous prefix sum can form a subarray with sum k.
This C implementation uses a hash table to track the occurrence of prefix sums, adjusted with an offset for negative indices safety, enabling identification of subarrays summing to k. The time complexity reduces to O(n), with space complexity also improving due to the hash table.