Katkat
Back

Count subarrays summing to target

TikTokMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize subarray sum calculations from an O(n^2) approach to O(n) using a hash map for prefix sum tracking.

Problem Statement

Given an array of integers nums and an integer target, return the total number of continuous subarrays that sum up to target.

Function Signature

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

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -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 arrays or arrays with a single element.
  • Negative numbers present in the input array.
  • Cases where no subarray sums to the target.

Hints

Hint 1

Consider the relationship between the cumulative sum at two different indices and the target value.

Hint 2

A subarray sum from index i to j can be represented as `prefix_sum[j] - prefix_sum[i-1]`.

Hint 3

Use a hash map (dictionary) to store the frequency of prefix sums encountered so far to achieve O(n) time complexity.

Follow-up questions

  • How would your approach change if you needed to return the actual indices of the subarrays rather than just the count?
  • What is the space complexity of your solution, and can it be improved?
  • If the array contained only non-negative integers, could you solve this problem using a sliding window (two-pointer) approach instead of a hash map?