Skip to main content

20. Subarray Sum Equals K

mediumAsked at Riot Games

Count contiguous subarrays whose sum equals k — Riot reaches for prefix-sum tricks when scanning telemetry streams for suspicious damage-windows.

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. Subarrays must be contiguous.

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. Nested sum

Compute every subarray sum with two loops.

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 hash map

Track running prefix sums in a hash map; for each index, add the count of (prefix - k) already seen. Riot uses the same scan to detect damage-window outliers in anti-cheat telemetry without quadratic loops.

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

Tradeoff:

Riot Games-specific tips

Riot grades for the prefix-sum-plus-hash-map jump and expects you to handle negative numbers explicitly — the same edge case their telemetry pipeline hits when champion heals interleave with damage events under lag compensation.

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

Practice these live with InterviewChamp.AI →