Count subarrays with sum equals k
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's competency in array algorithms and reasoning about contiguous subarray sums, including correct handling of negative and zero values.
Constraints
- 0 <= nums.length <= 20000
- -1000 <= nums[i] <= 1000
- -10000000 <= k <= 10000000
- Subarrays must be non-empty and contiguous
- nums may contain negative numbers and zeros
Examples
Input: ([1, 2, 3], 3)
Expected Output: 2
Explanation: The subarrays [1, 2] and [3] both sum to 3.
Input: ([1, -1, 0], 0)
Expected Output: 3
Explanation: The subarrays [1, -1], [1, -1, 0], and [0] sum to 0.
Input: ([0, 0, 0], 0)
Expected Output: 6
Explanation: All non-empty contiguous subarrays sum to 0. There are 3 single-element, 2 two-element, and 1 three-element subarrays.
Input: ([3, 4, 7, 2, -3, 1, 4, 2], 7)
Expected Output: 4
Explanation: The qualifying subarrays are [3, 4], [7], [7, 2, -3, 1], and [1, 4, 2].
Input: ([], 0)
Expected Output: 0
Explanation: There are no non-empty subarrays in an empty array.
Input: ([-2, -1, 2, 1], 1)
Expected Output: 2
Explanation: The subarrays [-1, 2] and [1] sum to 1.
Hints
- A sliding window is not reliable when negative numbers are allowed because the sum may increase or decrease unpredictably.
- Use prefix sums: if current_prefix - previous_prefix = k, then the subarray between those two prefix sums has sum k.