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 Akuna Capital.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Akuna Capital during technical interviews.

Count subarrays equal to target | Akuna Capital Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count subarrays equal to target states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count subarrays equal to target

Company: Akuna Capital

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an integer array nums and an integer k, count the number of contiguous subarrays whose sum equals k. Solve it in O(n) time and O(n) space by maintaining a running prefix sum and a hash map of prefix-sum frequencies. Explain why this works with negative numbers, analyze complexity, and provide code or pseudocode.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count subarrays equal to target states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an integer array `nums` and an integer `k`, count the number of contiguous (non-empty) subarrays whose elements sum to exactly `k`. Return the total count of such subarrays. Solve it in O(n) time and O(n) space by maintaining a running prefix sum and a hash map of prefix-sum frequencies. The map records how many times each prefix sum has occurred so far; at each index, the number of subarrays ending here with sum `k` equals the number of earlier prefixes equal to `prefix - k`. **Why it works with negative numbers:** Unlike a sliding-window approach, this method never assumes the running sum is monotonically increasing. It relies only on the algebraic identity `sum(i+1..j) = prefix[j] - prefix[i]`, which holds regardless of sign. The same prefix value can recur (e.g. after a `+1, -1`), and the frequency map counts every such occurrence, so subarrays formed by cancellation are all captured. Seeding the map with `{0: 1}` accounts for subarrays that start at index 0. **Examples:** - `nums = [1, 1, 1]`, `k = 2` -> `2` (the subarrays `[1,1]` at indices 0-1 and 1-2) - `nums = [1, 2, 3]`, `k = 3` -> `2` (`[1,2]` and `[3]`) - `nums = [1, -1, 1, -1]`, `k = 0` -> `4`

Constraints

1 <= nums.length <= 2 * 10^4 (an empty array yields 0)
-1000 <= nums[i] <= 1000 (values may be negative or zero)
-10^7 <= k <= 10^7
Subarrays are contiguous and non-empty; count every distinct index range that qualifies.

Examples

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

Expected Output: 2

Explanation: The two overlapping subarrays [1,1] (indices 0-1 and 1-2) each sum to 2.

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

Expected Output: 2

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

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

Expected Output: 4

Explanation: [1,-1] (twice), [-1,1], and the whole array [1,-1,1,-1] all sum to 0 — negatives produce repeated prefix sums.

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.

Input: ([], 0)

Expected Output: 0

Explanation: No elements means no non-empty subarrays, so the count is 0.

Input: ([5], 5)

Expected Output: 1

Explanation: The single subarray [5] matches k=5.

Input: ([5], 3)

Expected Output: 0

Explanation: The only subarray [5] sums to 5, not 3.

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

Expected Output: 1

Explanation: Only [-1,1] (indices 1-2) sums to 0; demonstrates correctness with all-negative prefixes.

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

Expected Output: 6

Explanation: Every one of the 6 contiguous subarrays of three zeros sums to 0, showing duplicate prefix sums are counted fully.

Hints

A subarray sum equals prefix[j] - prefix[i]. Fix the right end j and ask: how many earlier prefixes i satisfy prefix[j] - prefix[i] = k, i.e. prefix[i] = prefix[j] - k?
Keep a hash map from prefix-sum value to how many times it has occurred. Before inserting the current prefix, add freq[prefix - k] to your answer.
Seed the map with {0: 1} so subarrays that start at index 0 are counted. Because you query for prefix - k BEFORE inserting the current prefix, you never count an empty subarray.

Quick Overview