Skip to main content

24. Subarray Sum Equals K

mediumAsked at Tesla

Count subarrays whose values sum to a target — Tesla uses prefix-sum anomaly detection on vehicle telemetry streams to count windows where cumulative sensor drift exceeds a threshold, triggering a recalibration event in the sensor fusion pipeline.

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

Problem

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

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] (indices 0-1) and [1,1] (indices 1-2) both sum to 2.

Example 2

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

Approaches

1. Brute force O(n^2)

For every pair (i, j), compute the subarray sum and check if it equals k. No extra space, but quadratic 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

Store frequency of prefix sums seen so far. For each position, check how many previous prefix sums equal currentSum - k. Single pass, O(n).

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

Tradeoff:

Tesla-specific tips

Tesla uses continuous sensor data — gyroscope, accelerometer, radar — and needs to detect anomaly windows efficiently in real time. The prefix-sum trick is the key insight; many candidates never arrive at it without a nudge. Practice explaining it without jargon: 'If the sum from 0 to j equals k + sum from 0 to i, then the subarray from i+1 to j sums to k.' Note that sliding window does NOT work here because negative values break the monotonic-sum assumption — say that proactively.

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

Practice these live with InterviewChamp.AI →