Leetcode 560. Subarray Sum Equals K

Let's understand what we're being asked to do. We have an array like [1, 1, 1] and a target sum k = 2. We need to count how many contiguous subarrays sum to exactly 2.

Tracing through: subarray [1,1] (indices 0-1) sums to 2 ✓, subarray [1,1] (indices 1-2) also sums to 2 ✓. So the answer is 2.

Important constraint: The array can contain negative numbers, zero, and positive numbers. This means a subarray's sum can increase, decrease, or stay the same as we extend it!

Edge cases to consider: What if the entire array sums to k? What if k = 0 and we have zeros in the array? What if no subarray sums to k? What about subarrays of length 1?

The brute force approach checks all possible subarrays explicitly using nested loops. For each starting index i, iterate through all ending indices j >= i, computing the sum of elements from i to j. If the sum equals k, increment the count. This approach is straightforward but inefficient because it recalculates overlapping sums repeatedly and doesn't leverage any mathematical properties of prefix sums.

def subarray_sum(nums, k):
    """
    Count subarrays with sum equal to k using brute force.
    Check all possible contiguous subarrays explicitly.
    """
    count = 0
    n = len(nums)
    
    # Outer loop: iterate through all starting indices
    for i in range(n):
        current_sum = 0
        
        # Inner loop: iterate through all ending indices from i
        for j in range(i, n):
            # Add current element to sum
            current_sum += nums[j]
            
            # Check if sum equals k
            if current_sum == k:
                count += 1
    
    return count

For any subarray from index i to j, its sum equals prefixSum[j] - prefixSum[i-1]. If this equals k, then prefixSum[j] - prefixSum[i-1] = k, which means prefixSum[i-1] = prefixSum[j] - k.

This transforms the problem: at each position j, we ask 'how many previous positions had a prefix sum of exactly currentSum - k?'

By tracking prefix sums in a hash map with their frequencies, we can instantly look up how many previous positions would form a valid subarray ending at the current position.

This avoids checking all possible subarrays explicitly, which would be O(n²). Instead, we process each element once while maintaining running counts.

Imagine you're tracking your bank balance day by day. If you want to know 'on which days did I earn exactly $100?', you'd look at balance differences.

If today's balance is $500 and you want to find days where you earned $100 since then, you'd look for previous days with balance $500 - $100 = $400. The number of such days is how many ways you earned exactly $100 ending today.

The hash map stores 'how many times have I seen each balance before?' so you can instantly count matching previous balances.

The optimal approach uses cumulative prefix sums with a hash map to count matching subarrays in a single pass. As we iterate through the array, we maintain a running sum and store the frequency of each prefix sum seen so far. At each position, we check if currentSum - k exists in the hash map - if it does, those previous positions form valid subarrays ending at the current position. This works because if prefixSum[j] - prefixSum[i] = k, then prefixSum[i] = prefixSum[j] - k. We initialize the hash map with {0: 1} to handle subarrays starting from index 0.

def subarray_sum(nums, k):
    """
    Count subarrays with sum equal to k using prefix sums.
    Time: O(n), Space: O(n)
    """
    # Hash map to store frequency of prefix sums
    prefix_count = {0: 1}
    current_sum = 0
    count = 0
    
    # Iterate through array
    for num in nums:
        # Update running sum
        current_sum += num
        
        # Check if (current_sum - k) exists in map
        # If yes, those positions form valid subarrays
        if current_sum - k in prefix_count:
            count += prefix_count[current_sum - k]
        
        # Add current prefix sum to map
        if current_sum in prefix_count:
            prefix_count[current_sum] += 1
        else:
            prefix_count[current_sum] = 1
    
    return count

• Prefix sum with hashmap pattern: When you need to find subarrays with a specific sum and the array contains negative numbers (ruling out sliding window), use cumulative prefix sums stored in a hashmap - if `prefixSum - k` exists in the map, you've found subarrays ending at the current index.
• Frequency map over boolean tracking: Store the count/frequency of each prefix sum rather than just checking existence - multiple occurrences of the same prefix sum mean multiple valid subarrays, so `count += map.get(prefixSum - k)` captures all possibilities in one lookup.
• Initialize with base case: Always seed your hashmap with `map.put(0, 1)` before iterating - this handles subarrays that start from index 0 where the prefix sum itself equals k, a critical edge case that's easy to miss.
• Single-pass O(n) transformation: By maintaining a running sum and looking backward via hashmap (instead of checking all subarray combinations), you convert an O(n²) brute force into O(n) time with O(n) space - the hashmap trades space for dramatic time savings.
• Subarray sum decomposition principle: The key insight is that `sum(i, j) = prefixSum[j] - prefixSum[i-1]`, so finding subarrays summing to k becomes finding pairs where `prefixSum[j] - prefixSum[i-1] = k`, which rearranges to looking up `prefixSum[j] - k` in your history.
• Range query optimization pattern: This prefix sum + hashmap technique extends to any problem asking about contiguous subarray properties (sum equals k, divisible by k, difference equals target) - whenever you see 'subarray' with a target condition, consider if prefix sums can transform it into a lookup problem.