Count Subarrays with a Target Sum
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `count_target_subarrays(values, target)`.
Return the number of contiguous subarrays whose elements sum exactly to `target`. Values may be negative, zero, or positive. The empty subarray is not counted.
For example, `values = [1, 1, 1]` and `target = 2` produce `2`.
Target `O(n)` time and `O(n)` auxiliary space.
```hint Ask what earlier prefix is needed
If the current prefix sum is `p`, a target-sum subarray ending here begins after an earlier prefix sum of `p - target`.
```
```hint Seed the empty prefix
Record one occurrence of prefix sum zero before scanning so subarrays beginning at index zero are counted.
```
### Discussion Extensions
- Why does a sliding window fail when negative values are allowed?
- How should the implementation behave for an empty array, all zeros, or a zero target?
Quick Answer: Count contiguous subarrays whose sum equals a target in O(n) time, even when values are negative or zero. Use prefix-sum frequencies to count valid starts, including subarrays that begin at index zero.
Implement count_target_subarrays(values, target). Return the number of nonempty contiguous subarrays whose sum is exactly target, allowing negative, zero, and positive values.
Constraints
- 0 <= values.length <= 1,000.
- Each value is between -1,000,000,000 and 1,000,000,000.
- The target and every prefix sum fit in a signed 64-bit integer.
Examples
Input: ([1, 1, 1], 2)
Expected Output: 2
Input: ([1, -1, 0], 0)
Expected Output: 3
Hints
- At a current prefix sum p, a target-sum subarray starts after any earlier prefix equal to p - target.
- Seed prefix sum zero with frequency one so subarrays beginning at index zero are counted.