Katkat
Back

Count subarrays equal to target

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use a hash map to track prefix sums, allowing for an efficient solution to a subarray counting problem.

Count Subarrays with Target Sum

Given an array of integers nums and an integer target, return the total number of continuous subarrays whose sum equals the target.

Function Signature

def count_subarrays(nums: List[int], target: int) -> int:

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • -1000 <= nums[i] <= 1000
  • -10^7 <= target <= 10^7

Examples

Example 1: Input: nums = [1, 1, 1], target = 2 Output: 2 Explanation: The subarrays are [1, 1] (indices 0-1) and [1, 1] (indices 1-2).

Example 2: Input: nums = [1, 2, 3], target = 3 Output: 2 Explanation: The subarrays are [1, 2] (indices 0-1) and [3] (index 2).

Edge Cases

  • Empty array or array with one element.
  • Arrays containing negative numbers and zeros.
  • Cases where no subarray sums to the target.

Hints

Hint 1

Consider calculating the cumulative sum (prefix sum) at each index as you iterate through the array.

Hint 2

If the sum up to index `j` is `S_j` and the sum up to an earlier index `i` is `S_i`, the sum of the subarray from `i+1` to `j` is `S_j - S_i`.

Hint 3

Use a hash map to store the frequency of prefix sums encountered so far to check how many previous prefix sums equal `current_sum - target` in O(1) time.

Follow-up questions

  • How would you modify your solution if the array only contained non-negative integers?
  • What is the space complexity of your approach, and can it be optimized?
  • How would you handle the case where you need to find the length of the longest subarray that sums to the target?