The O(n) Club: Subarray Sum Equals K – But Make It Fashion

The O(n) Club: Subarray Sum Equals K – But Make It Fashion

⚡ TL;DR

Given an array and target k, count the number of CONTIGUOUS subarrays that sum to exactly k. Brute force might be your emotional support duck, but it drowns in O(n²):

// Brute force (friends don't let friends code like this)
int count = 0;
for (int i = 0; i < nums.length; i++) {
    int sum = 0;
    for (int j = i; j < nums.length; j++) {
        sum += nums[j];
        if (sum == k) count++;
    }
}

🧠 How Devs Usually Mess This Up

No shame—most of us try double for-loops first, thinking “Big-O can’t be THAT bad, right?” But when your LeetCode input is ‘thicc’, two nested loops will make your code sweat so hard it gets TLE’d out of the room. Bonus: People often mix up subarrays (contiguous) with subsequences (chaotic free-for-all picks). Don’t be that person.

🔍 What’s Actually Going On

The real magic: walk through the array with a running sum (prefix sum), but instead of living in the past, you use a HashMap to “remember” every sum you’ve ever hit. Whenever your running sum minus k shows up in this map, it means you’ve found a streak of numbers that sums to k. Like asking, “Did I have just enough snacks left then to eat exactly k by now?” Immediate results, no rewind button required.

🛠️ PseudoCode

• Start with a HashMap storing cumulative prefix sums and their counts:

  Map<Integer, Integer> map = new HashMap<>();
  map.put(0, 1); // Just in case you hit k right from the start

• Walk through the array, adding each number to the sum:

  int sum = 0;
  for (int num : nums) {
      sum += num;
      // (rest of the algorithm...)
  }

• For each step, if sum - k exists in the map, add its value to the answer — because you just hit another subarray-ending jackpot.

  if (map.containsKey(sum - k)) {
      count += map.get(sum - k);
  }

• Remember the current sum for later:

  map.put(sum, map.getOrDefault(sum, 0) + 1);

💻 The Code

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        count += map.getOrDefault(sum - k, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No-commit subarrays: Only contiguous elements count, not sequenced pick-and-mix.
• Negatives/Zeroes: Don’t sweat it — prefix sums + HashMap laughs at negative numbers and zeroes alike.
• Forgot to map.put(0,1): You’ll miss subarrays starting at 0 — and your count will be sad.
• Time/Space: O(n) for both. If n is gigantic and most prefix sums are unique (rare), the map gets chunky but stays cool under pressure.

🧠 Interviewer Brain-Tattoo

“Don’t trust brute force. Trust your memory—and your map. The past matters when you actually remember it.”