Count Subarrays with a Target Sum

Question

The question asks the candidate to implement a solution that counts the number of contiguous subarrays within a given array that sum up to a specified target value.

Codemia · Accepted Answer

To count the number of contiguous subarrays that sum up to a target value, we can utilize a hash map to store the cumulative sum of elements as we iterate through the array. This allows us to efficiently check if there exists a previous cumulative sum that, when subtracted from the current cumulative sum, equals the target.

1. Initialize a hash map to store cumulative sums and their frequencies.
2. Initialize a variable to keep track of the current cumulative sum and a counter for the number of valid subarrays.
3. Iterate through the array, updating the cumulative sum at each step.
4. For each cumulative sum, check if the difference between the current cumulative sum and the target exists in the hash map. If it does, increment the counter by the frequency of that difference.
5. Update the hash map with the current cumulative sum.

The time complexity of this approach is O(n) since we traverse the array once, and the hash map operations (insert and lookup) are O(1) on average. The space complexity is also O(n) in the worst case, where all cumulative sums are unique.

```python
from collections import defaultdict

def count_subarrays_with_target_sum(arr, target):
    cumulative_sum = 0
    count = 0
    sum_map = defaultdict(int)
    sum_map[0] = 1  # To handle the case where cumulative sum equals target

for num in arr:
        cumulative_sum += num
        if cumulative_sum - target in sum_map:
            count += sum_map[cumulative_sum - target]
        sum_map[cumulative_sum] += 1

return count
```

Consider edge cases such as an empty array, an array with all negative numbers, or when the target sum is zero. The implementation should handle these cases gracefully, ensuring that the count reflects the correct number of valid subarrays.

Count Subarrays with a Target Sum

Meta

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

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