Count subarrays summing to target

Q: Count subarrays summing to target

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

Q: What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Question

##### 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/

PracHub · Accepted Answer

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

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.

Quick Overview

Count subarrays summing to target

Constraints

Solution

Explanation

Hints