Subarray Sum Equals K

Question

Given an array of integers and a target k, find the total number of contiguous subarrays whose sum equals k. Tests prefix sum and hash map patterns frequently seen at Meta.

Codemia · Accepted Answer

To solve the problem of finding the total number of contiguous subarrays whose sum equals k, we can leverage the prefix sum technique combined with a hash map. The prefix sum allows us to compute the sum of any subarray efficiently. The key insight here is that if we have a prefix sum at index j and we want to find all subarrays ending at j that sum to k, we can check if there exists a prefix sum at index i (where i < j) such that `prefix_sum[j] - prefix_sum[i] = k`. This can be rearranged to `prefix_sum[i] = prefix_sum[j] - k`. Therefore, we can use a hash map to store the frequency of prefix sums as we iterate through the array, allowing us to quickly check how many times the required prefix sum has occurred.

1. Initialize a hash map (or dictionary) to store the frequency of prefix sums, starting with {0: 1} to account for any subarrays that sum to k starting from the first element.
2. Initialize two variables: `current_sum` to keep track of the running sum as you iterate through the array, and `count` to store the total number of valid subarrays.
3. Iterate through the array:
   - For each element, update `current_sum` by adding the current element.
   - Check if `(current_sum - k)` exists in the hash map. If it does, it means there are subarrays ending at the current index that sum to k; add the frequency of `(current_sum - k)` to `count`.
   - Update the hash map to include the current `current_sum` by incrementing its count.
4. Return the count as the result.

**Example**: Given the array [1, 1, 1] and k = 2:
- Initialize: `prefix_sum = {0: 1}`, `count = 0`, `current_sum = 0`.
- Iterating through the array:
  - For index 0: `current_sum = 1`, check if `1 - 2 = -1` exists in the map (it does not). Update map: `prefix_sum = {0: 1, 1: 1}`.
  - For index 1: `current_sum = 2`, check if `2 - 2 = 0` exists (it does, frequency = 1). Increment count by 1. Update map: `prefix_sum = {0: 1, 1: 1, 2: 1}`.
  - For index 2: `current_sum = 3`, check if `3 - 2 = 1` exists (it does, frequency = 1). Increment count by 1. Update map: `prefix_sum = {0: 1, 1: 1, 2: 1, 3: 1}`.
- Final count = 2.

Here is the Python solution for the problem:

```python
def subarraySum(nums, k):
    prefix_sum = {0: 1}
    count = 0
    current_sum = 0
    for num in nums:
        current_sum += num
        if (current_sum - k) in prefix_sum:
            count += prefix_sum[current_sum - k]
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    return count
```

This code efficiently counts the number of subarrays whose sum is equal to k by utilizing the prefix sum and a hash map to track occurrences.

The time complexity of this solution is O(n), where n is the length of the input array. This is because we are iterating through the array once and performing O(1) operations for each element (hash map lookups and updates). The space complexity is also O(n) in the worst case, as the hash map may store a unique prefix sum for each element in the array.

1. **Empty Array**: If the input array is empty, the result should be 0 since there are no subarrays.
2. **All Elements Zero**: If all elements in the array are zero and k is zero, the number of subarrays will be substantial. For example, for array [0, 0, 0] and k = 0, the output should be 6, as there are multiple combinations of subarrays summing to zero.
3. **Negative Numbers**: The algorithm should correctly handle negative numbers. For example, with array [-1, -1, 1] and k = 0, the output should be 1, as the subarray [-1, 1] sums to zero.
4. **No Valid Subarrays**: If there are no subarrays that sum to k, the function should return 0.

Subarray Sum Equals K

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string