Count subarrays summing to target
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 560. Subarray Sum Equals K – Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals k. Variants:
(a) return a boolean indicating whether any such subarray exists,
(b) if all numbers are positive, achieve O(
1) extra space using the sliding-window technique.
https://leetcode.com/problems/subarray-sum-equals-k/description/
Quick Answer: This question evaluates a candidate's understanding of array algorithms, cumulative-sum reasoning, and time/space complexity considerations when identifying subarrays with a target sum. Commonly asked in the Coding & Algorithms domain to probe algorithmic problem-solving, data-structure reasoning, and optimization skills, it targets practical application rather than purely conceptual theory.
Given an integer array nums and an integer k, return the number of non-empty contiguous subarrays whose sum equals k. nums may contain negative numbers and zeros. Return the count as an integer.
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= k <= 10^9
- Subarrays are contiguous and non-empty
- Result may exceed 32-bit integer range
Solution
from typing import List
from collections import defaultdict
def count_subarrays_sum_k(nums: List[int], k: int) -> int:
"""
Returns the number of non-empty contiguous subarrays whose sum equals k.
Uses prefix sums with a frequency map.
"""
count = 0
prefix = 0
freq = defaultdict(int)
freq[0] = 1
for x in nums:
prefix += x
count += freq[prefix - k]
freq[prefix] += 1
return count
Explanation
Maintain a running prefix sum. For each prefix sum s at index i, any previous index j with prefix sum s - k yields a subarray (j+1..i) summing to k. Count how many such previous sums exist using a hash map. Initialize the map with 0 mapped to 1 to account for subarrays starting at index 0.
Time complexity: O(n). Space complexity: O(n).
Hints
- Use a running prefix sum and a hash map storing frequencies of prefix sums seen so far.
- If current prefix is s, then the number of subarrays ending here with sum k equals the frequency of (s - k).
- Initialize the map with {0: 1} to count subarrays that start at index 0.
- If all numbers are positive, a sliding window achieves O(1) extra space, but it does not work with negative numbers.