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.

What difficulty level is this coding question?

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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Count subarrays summing to target | Meta Coding Question

Count subarrays summing to target

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an integer array nums and an integer target T, return the number of contiguous subarrays whose sum equals T. Provide an algorithm that runs in linear time using appropriate data structures, and explain how it handles negative numbers and edge cases (e.g., T = 0, empty prefix). Analyze time and space complexity.

Quick Answer: This question evaluates understanding of prefix-sum concepts, use of linear-time data structures, and competence in handling negative numbers and edge cases such as zero targets and empty prefixes.

Given an integer array `nums` and an integer `target`, return the total number of contiguous subarrays whose elements sum exactly to `target`. A subarray is a contiguous (non-empty) slice of the array. Two subarrays that occupy different index ranges count separately even if they contain the same values. The array may contain negative numbers, zeros, and duplicates, so a sliding-window approach does not work. Aim for an O(n) time solution. **Example 1:** ``` Input: nums = [1, 1, 1], target = 2 Output: 2 Explanation: The subarrays [1,1] (indices 0..1) and [1,1] (indices 1..2) each sum to 2. ``` **Example 2:** ``` Input: nums = [1, 2, 3], target = 3 Output: 2 Explanation: [1,2] and [3] both sum to 3. ``` **Example 3:** ``` Input: nums = [0, 0, 0], target = 0 Output: 6 Explanation: Every one of the C(3+1, 2) = 6 contiguous ranges sums to 0. ```

Constraints

1 <= nums.length <= 2 * 10^4 (an empty array trivially returns 0)
-1000 <= nums[i] <= 1000
-10^7 <= target <= 10^7
The array may contain negatives, zeros, and duplicate values.

Examples

Input: ([1, 1, 1], 2)

Expected Output: 2

Explanation: Subarrays [1,1] at indices 0..1 and [1,1] at indices 1..2 each sum to 2.

Input: ([1, 2, 3], 3)

Expected Output: 2

Explanation: [1,2] and [3] both sum to 3.

Input: ([], 0)

Expected Output: 0

Explanation: An empty array has no non-empty subarrays, so the count is 0.

Input: ([0, 0, 0], 0)

Expected Output: 6

Explanation: All 6 contiguous ranges of a length-3 array sum to 0; the seeded {0:1} prefix lets ranges starting at index 0 be counted.

Input: ([-1, -1, 1], 0)

Expected Output: 1

Explanation: Only [-1, 1] at indices 1..2 sums to 0, demonstrating correct handling of negatives where a sliding window would fail.

Input: ([3, 4, 7, 2, -3, 1, 4, 2], 7)

Expected Output: 4

Explanation: [3,4], [7], [7,2,-3,1], and [1,4,2] each sum to 7 — note overlaps and a span crossing a negative value.

Input: ([5], 5)

Expected Output: 1

Explanation: Single-element array equal to the target counts once.

Input: ([1, -1, 1, -1], 0)

Expected Output: 4

Explanation: [1,-1] (idx 0..1), [1,-1] (idx 2..3), [-1,1] (idx 1..2), and [1,-1,1,-1] (idx 0..3) all sum to 0.

Hints

Define prefix[i] = nums[0] + ... + nums[i-1]. A subarray (l, r) sums to target exactly when prefix[r+1] - prefix[l] == target.
Rearrange: for each running prefix sum S, you need the count of earlier prefix sums equal to S - target. Maintain a hash map from prefix-sum value to how many times it has occurred so far.
Seed the map with {0: 1} before the loop. That entry represents the empty prefix and is what lets a subarray starting at index 0 be counted (it handles target sums that begin at the very front, including target = 0).
Because you only ever look at prefix sums seen *before* the current index, the method works correctly with negative numbers and zeros where sliding windows fail.

Quick Overview

This question evaluates understanding of prefix-sum concepts, use of linear-time data structures, and competence in handling negative numbers and edge cases such as zero targets and empty prefixes.