Skip to main content

560. Subarray Sum Equals K

mediumAsked at Atlassian

Subarray Sum Equals K is an Atlassian-favorite prefix-sum + hash-map problem. Given an integer array and an integer k, return the total number of subarrays whose sum equals k. The unsigned reveal is that prefix sums + hash map is the optimal — sliding window fails when negatives appear.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Subarray Sum Equals K as a recurring prefix-sum problem at round 2 or 3.
  • Blind (2025-11)— Atlassian threads describe Subarray Sum Equals K as 'the trap that catches sliding-window habit'.

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 within an array.

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: [1,1] at indices 0-1 and 1-2.

Example 2

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

Explanation: [3] and [1,2].

Approaches

1. Brute O(n^2)

For each start i, accumulate sum forward and count whenever sum == k.

Time
O(n^2)
Space
O(1)
function subarraySumBrute(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: Passes the LeetCode judge at n=2*10^4 (4*10^8 ops borderline). Use it only to motivate the optimal — show you noticed the redundant recomputation across the i loop.

2. Prefix sum + hash map (optimal)

Track running prefix sum S. The number of subarrays ending at i with sum k equals the number of earlier indices j where prefix[j] == S - k. Use a counts map for O(1) lookup.

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const counts = new Map();
  counts.set(0, 1);
  let sum = 0, result = 0;
  for (const n of nums) {
    sum += n;
    if (counts.has(sum - k)) result += counts.get(sum - k);
    counts.set(sum, (counts.get(sum) || 0) + 1);
  }
  return result;
}

Tradeoff: The Atlassian-canonical answer. The crucial pre-seed is counts.set(0, 1) — it accounts for subarrays starting at index 0. Forget that and the count is off by however many subarrays start from index 0.

Atlassian-specific tips

Atlassian interviewers explicitly test the sliding-window trap on this problem. If you propose sliding window, they'll wait — then construct an input with negatives (e.g., [1,-1,1], k=1) where sliding window can't recover because shrinking from the left can DECREASE the sum, not just increase. State this trap upfront — 'I thought of sliding window, but negative values mean window-shrink doesn't monotonically reduce the sum, so I need prefix-sum + hash map'. That's the load-bearing rubric point.

Common mistakes

  • Forgetting counts.set(0, 1) — silently misses subarrays starting at index 0.
  • Looking up counts.get(sum - k) AFTER updating counts for sum — that would count the current prefix as a candidate for itself when k=0.
  • Trying sliding window despite negatives — the moment the array has a negative element this approach breaks.

Follow-up questions

An interviewer at Atlassian may pivot to one of these next:

  • Continuous Subarray Sum (LeetCode 523) — count subarrays whose sum is divisible by k; store prefix mod k.
  • Subarray Sum Equals K with positive integers only — sliding window works in O(n) time, O(1) space.
  • Maximum subarray sum with sum >= k — different family of problems; mention Kadane's variants.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why doesn't sliding window work here?

Sliding window requires the sum to be monotonic in window size — grow right increases sum, shrink left decreases. With negative numbers shrinking the left can INCREASE the sum (if you remove a negative), so you can't decide which direction to move. Prefix sum sidesteps this by precomputing all window sums via a running total.

What's the role of counts.set(0, 1)?

It treats 'no elements' as a valid empty prefix with sum 0. When the running sum first equals k itself, sum - k = 0 must be findable in the map — and the empty prefix is the only way to get sum 0 with zero elements taken.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →