Count subarrays equal to target
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum equals k. Provide an algorithm better than O(n^
2), explain time and space complexity, and describe how your approach handles negative numbers, zeros, very large arrays, and integer overflow concerns.
Quick Answer: This question evaluates array manipulation, cumulative-sum reasoning, and algorithmic complexity analysis for counting contiguous subarrays that equal a target value.
Given an integer array `nums` and an integer `k`, return the number of contiguous (non-empty) subarrays whose elements sum to exactly `k`.
A subarray is a contiguous slice of the array. Two subarrays at different start/end positions are counted separately even if their contents are identical.
Your algorithm must run better than O(n^2). The intended solution uses prefix sums and a hash map: keep a running prefix sum `s` while scanning left to right, and for each position add the number of earlier prefix sums equal to `s - k` (initializing the count of prefix sum 0 to 1 so that subarrays starting at index 0 are counted). This is O(n) time and O(n) space.
The approach naturally handles negative numbers and zeros (a sliding window would NOT, because the running sum is not monotonic). For very large arrays it stays linear, and the running/prefix sums should use a 64-bit integer type to avoid overflow when many large values accumulate.
Example 1: nums = [1, 1, 1], k = 2 -> 2 (the subarrays [1,1] at indices 0-1 and 1-2).
Example 2: nums = [1, 2, 3], k = 3 -> 2 (the subarrays [1,2] and [3]).
Example 3: nums = [0, 0, 0], k = 0 -> 6 (every one of the C(3,2)+3 = 6 contiguous slices sums to 0).
Constraints
- 1 <= nums.length <= 2 * 10^4 (an empty array yields 0)
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
- Prefix sums can reach magnitudes around 2 * 10^7, well within 32-bit range, but use a 64-bit accumulator if element bounds are widened
Examples
Input: ([1, 1, 1], 2)
Expected Output: 2
Explanation: The subarrays [1,1] at indices 0-1 and at indices 1-2 each sum to 2.
Input: ([1, 2, 3], 3)
Expected Output: 2
Explanation: [1,2] sums to 3 and the single element [3] sums to 3.
Hints
- A sliding window does not work here because negative numbers and zeros make the running sum non-monotonic — shrinking the window can both decrease and increase the sum.
- Define prefix[i] = nums[0] + ... + nums[i-1]. A subarray (i, j] sums to k exactly when prefix[j] - prefix[i] = k, i.e. prefix[i] = prefix[j] - k.
- Scan left to right keeping a running prefix sum and a hash map from prefix-sum value to how many times it has occurred. For each position add map[running_sum - k] to the answer, then record the current running_sum.
- Seed the map with {0: 1} before the loop so that subarrays starting at index 0 (where prefix[i] = 0) are counted.