Skip to main content

560. Subarray Sum Equals K

mediumAsked at Bloomberg

Bloomberg's compliance team counts how many consecutive trading windows sum to a target P&L threshold — this is exactly the subarray-sum problem, and the prefix-sum hash-map trick cuts the search from O(n^2) to a single pass every real-time analyst depends on.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k. A subarray is a contiguous non-empty sequence of elements.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Examples

Example 1

Input
nums = [1,1,1], k = 2
Output
2

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

Example 2

Input
nums = [1,2,3], k = 3
Output
2

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

Approaches

1. Brute force (all subarrays)

For each starting index, accumulate the running sum and count hits when it equals k. O(n^2) time.

Time
O(n^2)
Space
O(1)
function subarraySum(nums, k) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) count++;
    }
  }
  return count;
}

Tradeoff:

2. Prefix sum with hash map (optimal)

Track the running prefix sum. For each index, check if (prefixSum - k) has been seen before — if so, those earlier positions each start a valid subarray ending here. Store prefix-sum frequencies in a map.

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const freq = new Map([[0, 1]]);
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += freq.get(sum - k) || 0;
    freq.set(sum, (freq.get(sum) || 0) + 1);
  }
  return count;
}

Tradeoff:

Bloomberg-specific tips

This problem appears often in Bloomberg's quant and data-engineering rounds because the prefix-sum pattern is foundational to time-series window queries. The key insight Bloomberg interviewers want to hear: initialize the map with {0: 1} to handle subarrays starting at index 0. Skipping that initialization is the most common silent bug — demonstrate you know it by explaining why before you code. Follow-up: 'can the subarray contain negative numbers?' Yes, and your prefix-sum solution handles it correctly, unlike the sliding-window approach.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Subarray Sum Equals K and other Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →