Subarray Sum Equals K

Finding how many contiguous stretches of transactions sum to a target turns up in budgeting tools, analytics dashboards, and real‑time monitoring. It’s a great exercise in prefix sums and hash maps—key techniques for any software engineer.

Problem Statement

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

// Function signature in a technical interview:
public int subarraySum(int[] nums, int k);

1. Clarify Requirements Before Jumping Into Code

• Can array elements be negative, zero, or positive? Yes, all three.

• Is k allowed to be negative or zero? Yes.

• Do we count overlapping subarrays separately? Yes.

• Expected time/space? Aim for better than O(n²) if possible.

2. Identify the Category of the Question

This is a prefix‑sum and hash‑map problem on arrays. Common patterns:

• Sliding window for all‑positive arrays

• Prefix sums to convert subarray sums into differences of two cumulative sums

• Hash map to count how many times a prefix sum has appeared

Because negatives break sliding‑window monotonicity, prefix sums with a map is the go‑to.

3. Consider a Brute‑Force Approach to Understand the Problem

I can simply iterate through the array and calculate the sums of all the elements that follow it, essentially comparing every element against every other element in the array.

• Time: O(n²)

• Space: O(1)

• Too slow when n is in the tens of thousands.

  
  

4. Brainstorm More Solutions

Let's break the problem down:

1. Simplify input: What if all numbers are nonnegative? Then a sliding‑window (two pointers) can find subarrays in O(n). I’d shrink or grow the window based on the running sum.

2. Reintroduce negatives: The sliding window fails if negatives can decrease the sum unexpectedly, but maybe I can reuse the basic idea here. Is there a way for me to keep track of the sum so far so that I don't have to recompute every window? What would that look like?

   • Let's say I have an array P to keep track of my sums so far.

     • P[i] = sum of nums[0..i-1].

   • But what if I'm not starting my count at 0? What if want to start counting at some element j? i.e., I want to compute the sum of a subarray j->i?

     • Another way to think about this is if I know the sum of nums[0.. i-1] (which is P[i]), then I need to subtract all of the numbers that were in nums[0..j-1].

     • But we already know the sum of nums[0..j-1]! That's the number we're storing in P[j]!

     • In other words, the sum of nums[j..i-1] is equal to P[i] – P[j].

   • So we have found a subarray that meets our conditions when P[i] – P[j] = k. Since we will always have P[i] and k on hand when we're iterating through nums, and will be looking for P[j], let's rearrange his to P[j] = P[i] – k.

   • Let's call this solution prefix-sums.

3. Count matching prefixes: Now as I as I scan and compute P[i], I don't want to have to compare against every other element in P to find every P[j] that equals P[i] - k.

   • It would save time if I had fast lookups to figure out how many times I've seen P[i] – k.

   • What's great for fast lookups? A hash map!

   • What would the key and value be? The key should be P[i] - k. The value should be count of occurrences! Now I can look up constant time how many times I've seen P[i]-k

4. Summarizing:

   • Initialize map = {0:1} because a prefix sum of 0 occurs once at the imaginary P[0].

   • Running count = 0, sum = 0.

   • For each num in nums:

     1. sum += num (this is P[i]).

     2. If (sum – k) is in map, add map.get(sum – k) to the count.

     3. Update the map for the current sum: map[sum] += 1.

This runs in O(n) time and O(n) space for the map.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Brute‑force nested loops	O(n²)	O(1)	Trivial to implement	Too slow for large n
Sliding window (positives)	O(n)	O(1)	Very fast when all nums ≥ 0	Fails if negative numbers present
Prefix sums + array search	O(n²)	O(n)	Uses prefix sums, simpler logic	Still O(n²) searching prefixes
Prefix sums + hash map	O(n)	O(n)	Handles negatives, true O(n)	Extra map overhead

The prefix‑sum + hash‑map approach is optimal for the general case.

6. Write Pseudocode to Structure Your Thoughts

function subarraySum(nums, k):
  map = { 0: 1 }       // prefix sum 0 seen once
  count = 0
  sum = 0
  for num in nums:
    sum += num
    if (sum - k) in map:
      count += map[sum - k]
    map[sum] = map.get(sum, 0) + 1
  return count

7. Consider Edge Cases

• Empty array → returns 0.

• Single element equal to k → returns 1.

• Single element not equal to k → returns 0.

• All zeros, k = 0: with [0,0,0], there are 6 subarrays—map logic counts overlapping zeros correctly.

• Large negatives and positives → sum never overflows a 32‑bit int if within constraints.

8. Write Full Code Syntax (in Java)

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);   // one way to have sum=0 before starting
        int count = 0, sum = 0;
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Test 1: simple match
    assert sol.subarraySum(new int[]{1, 1, 1}, 2) == 2;
      // subarrays [1,1] at indices (0,1) and (1,2)

    // Test 2: negative and positive
    assert sol.subarraySum(new int[]{1, -1, 1, -1, 1}, 0) == 4;
      // sums of length-2 subarrays at various positions

    // Test 3: single element equal to k
    assert sol.subarraySum(new int[]{5}, 5) == 1;

    // Test 4: single element not equal
    assert sol.subarraySum(new int[]{5}, 3) == 0;

    // Test 5: all zeros, k = 0
    // subarrays of [0,0,0]: 6 total (n·(n+1)/2)
    assert sol.subarraySum(new int[]{0, 0, 0}, 0) == 6;

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Split into subproblems: recognize how to test one subarray, then scale to many.

• Prefix‑sum + hash‑map is the go‑to for arbitrary integers and target sums.

• Initialize map with {0:1} to count subarrays starting at index 0.

• Writing clear pseudocode first helps prevent off‑by‑one and map‑initialization bugs.

Good Luck and Happy Coding!