Skip to main content

22. Subarray Sum Equals K

mediumAsked at N26

Count the number of contiguous subarrays whose sum equals k. N26 asks this because their AML rules flag any contiguous window of transactions summing to a structuring threshold.

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

Problem

Given an array of integers nums and an integer k, return the total number of contiguous subarrays whose sum equals k. Negative numbers are allowed.

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

Example 2

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

Approaches

1. Two nested loops

For each start index, expand right and sum until you reach k or overflow.

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

Tradeoff:

2. Prefix sum with hash map

Track prefix sums and count how many times each has appeared. For each new prefix p, subarrays ending here that sum to k start at any index where prefix was p-k.

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

Tradeoff:

N26-specific tips

N26 cares that you map this to their AML structuring detector - any continuous window of deposits whose sum hits the 10k EUR reporting threshold has to be counted and surfaced to compliance.

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 N26 interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →