Katkat
Back

Count Subarrays with a Target Sum

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests the ability to use prefix sums and hash tables to count contiguous subarrays summing to a target in linear time, handling negative values and zeros.

Count Subarrays with a Target Sum

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

A contiguous subarray is a non-empty sequence of elements from the original array that appear in unbroken succession.

Function Signature

def count_subarrays_with_sum(nums: list[int], target: int) -> int:
    pass

Input and Output

  • Input: An array of integers nums and an integer target.
  • Output: An integer representing the count of contiguous subarrays whose elements sum to target.

Constraints

  • 1 <= len(nums) <= 10^5
  • -1000 <= nums[i] <= 1000
  • -10^7 <= target <= 10^7

Examples

Example 1:

Input: nums = [1, 1, 1], target = 2
Output: 2
Explanation: Subarrays [1, 1] at indices [0, 1] and [1, 2] both sum to 2.

Example 2:

Input: nums = [1, -1, 0], target = 0
Output: 3
Explanation: The subarrays summing to 0 are:
- [1, -1] from index 0 to 1
- [0] from index 2 to 2
- [1, -1, 0] from index 0 to 2

Edge Cases to Consider

  • Elements can be negative, zero, or positive, meaning running sums are not strictly monotonic.
  • Subarrays that begin at index 0 and sum to target.
  • Large numbers of zeros creating multiple overlapping zero-sum subarrays.

Hints

Hint 1

If you maintain a running cumulative sum, the sum of any subarray from index i to j is prefix_sum[j] - prefix_sum[i - 1].

Hint 2

At each index j, the problem reduces to checking how many previous prefix sums equal prefix_sum[j] - target.

Hint 3

Initialize your frequency table with a count of 1 for prefix sum 0 so subarrays starting at index 0 are counted correctly.

Follow-up questions

  • How would you solve this with O(1) auxiliary space if all elements in the array were strictly positive?
  • How would you modify the solution to return the maximum length of a subarray that sums to target rather than the count?
  • If the array is too large to fit in memory and is streamed chunk by chunk, how would you design the counting process?