560. Subarray Sum Equals K

Problem Statement

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

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: The subarrays [1,1] and [1,1] sum to 2.

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: The subarrays [1,2] and [3] sum to 3.

Example 3:

Input: nums = [1,-1,0], k = 0
Output: 3
Explanation: The subarrays [1,-1], [-1,0], and [1,-1,0] sum to 0.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Subarray definition: What constitutes a subarray? (Assumption: A contiguous non-empty sequence of elements - must be consecutive elements)

  2. Target sum: Can the target sum k be negative? (Assumption: Yes - k can be any integer, including negative values)

  3. Empty subarray: Should we consider empty subarrays? (Assumption: No - subarray must be non-empty, so length is at least 1)

  4. Overlapping subarrays: If multiple subarrays sum to k, should we count all of them? (Assumption: Yes - count all distinct subarrays that sum to k, even if they overlap)

  5. Zero sum: What if k = 0? (Assumption: Count all subarrays that sum to 0, including those with negative and positive numbers that cancel out)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

For each starting position i, iterate through all ending positions j >= i, calculate the sum of subarray nums[i..j], and increment count if sum equals k. This approach has O(n²) time complexity and O(1) space complexity.

Step 2: Semi-Optimized Approach (7 minutes)

Use prefix sums to avoid recalculating subarray sums. For each position, we can compute the sum from index 0 to current position. However, we still need to check all pairs of positions, which is still O(n²) time.

Step 3: Optimized Solution (8 minutes)

Use prefix sum with hash map. The key insight is: if prefixSum[i] - prefixSum[j] = k, then nums[j+1..i] sums to k. We can use a hash map to count occurrences of each prefix sum. For each position, check how many times prefixSum - k has appeared before. This achieves O(n) time and O(n) space complexity.

Solution Approach

This problem is a classic application of the prefix sum technique combined with hash map counting. The key insight is that if we have prefix sums, we can find subarrays with a target sum efficiently by counting occurrences.

Key Insights:

  1. Prefix Sum Property: sum(nums[i..j]) = prefixSum[j] - prefixSum[i-1]
  2. Hash Map Counting: Count occurrences of each prefix sum to handle multiple subarrays
  3. Initial State: Initialize with prefixSum[0] = 1 to handle subarrays starting from index 0

Solution: Prefix Sum with Hash Map

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0, sum = 0;
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        for(int num: nums) {
            sum += num;
            if(prefixSum.contains(sum - k)) {
                cnt += prefixSum[sum - k];
            }
            prefixSum[sum]++;
        }
        return cnt;
    }
};

Algorithm Breakdown:

  1. Initialize:
    • cnt = 0: Count of subarrays summing to k
    • sum = 0: Running prefix sum
    • prefixSum[0] = 1: Initialize with prefix sum 0 (for subarrays starting at index 0)
  2. Iterate: For each number in the array:
    • Update running sum: sum += num
    • Check if sum - k exists in map: If yes, add its count to cnt
    • Increment count for current prefix sum: prefixSum[sum]++
  3. Return: Total count of subarrays summing to k

Why This Works:

  • Prefix Sum Property: sum(nums[j+1..i]) = prefixSum[i] - prefixSum[j] = k
  • Rearranging: prefixSum[j] = prefixSum[i] - k
  • Counting: For each position i, count how many previous positions j have prefixSum[j] = prefixSum[i] - k
  • Initial State: prefixSum[0] = 1 handles the case where subarray starts at index 0

Sample Test Case Run:

Input: nums = [1,1,1], k = 2

Initial: cnt = 0, sum = 0, prefixSum = {0: 1}

Iteration 0 (num = 1):
  sum = 0 + 1 = 1
  prefixSum.contains(1 - 2 = -1)? No ✗
  prefixSum[1] = 1
  State: cnt=0, sum=1, prefixSum={0:1, 1:1}

Iteration 1 (num = 1):
  sum = 1 + 1 = 2
  prefixSum.contains(2 - 2 = 0)? Yes ✓ (count=1)
  cnt = 0 + 1 = 1
  prefixSum[2] = 1
  State: cnt=1, sum=2, prefixSum={0:1, 1:1, 2:1}

Iteration 2 (num = 1):
  sum = 2 + 1 = 3
  prefixSum.contains(3 - 2 = 1)? Yes ✓ (count=1)
  cnt = 1 + 1 = 2
  prefixSum[3] = 1
  State: cnt=2, sum=3, prefixSum={0:1, 1:1, 2:1, 3:1}

Return: cnt = 2 ✓

Verification:

  • Subarray [1,1] (indices 0-1): sum = 1 + 1 = 2 ✓
  • Subarray [1,1] (indices 1-2): sum = 1 + 1 = 2 ✓
  • Total count = 2 ✓

Output: 2 ✓

Another Example: nums = [1,2,3], k = 3

Initial: cnt = 0, sum = 0, prefixSum = {0: 1}

Iteration 0 (num = 1):
  sum = 0 + 1 = 1
  prefixSum.contains(1 - 3 = -2)? No ✗
  prefixSum[1] = 1
  State: cnt=0, sum=1, prefixSum={0:1, 1:1}

Iteration 1 (num = 2):
  sum = 1 + 2 = 3
  prefixSum.contains(3 - 3 = 0)? Yes ✓ (count=1)
  cnt = 0 + 1 = 1
  prefixSum[3] = 1
  State: cnt=1, sum=3, prefixSum={0:1, 1:1, 3:1}

Iteration 2 (num = 3):
  sum = 3 + 3 = 6
  prefixSum.contains(6 - 3 = 3)? Yes ✓ (count=1)
  cnt = 1 + 1 = 2
  prefixSum[6] = 1
  State: cnt=2, sum=6, prefixSum={0:1, 1:1, 3:1, 6:1}

Return: cnt = 2 ✓

Verification:

  • Subarray [1,2] (indices 0-1): sum = 1 + 2 = 3 ✓
  • Subarray [3] (indices 2-2): sum = 3 = 3 ✓
  • Total count = 2 ✓

Output: 2 ✓

Edge Case: nums = [1,-1,0], k = 0

Initial: cnt = 0, sum = 0, prefixSum = {0: 1}

Iteration 0 (num = 1):
  sum = 0 + 1 = 1
  prefixSum.contains(1 - 0 = 1)? No ✗
  prefixSum[1] = 1
  State: cnt=0, sum=1, prefixSum={0:1, 1:1}

Iteration 1 (num = -1):
  sum = 1 + (-1) = 0
  prefixSum.contains(0 - 0 = 0)? Yes ✓ (count=1)
  cnt = 0 + 1 = 1
  prefixSum[0] = 2 (increment existing)
  State: cnt=1, sum=0, prefixSum={0:2, 1:1}

Iteration 2 (num = 0):
  sum = 0 + 0 = 0
  prefixSum.contains(0 - 0 = 0)? Yes ✓ (count=2)
  cnt = 1 + 2 = 3
  prefixSum[0] = 3 (increment existing)
  State: cnt=3, sum=0, prefixSum={0:3, 1:1}

Return: cnt = 3 ✓

Verification:

  • Subarray [1,-1] (indices 0-1): sum = 1 + (-1) = 0 ✓
  • Subarray [-1,0] (indices 1-2): sum = -1 + 0 = -1 ✗ (Wait, let me recalculate)
  • Actually: [-1,0] sum = -1 + 0 = -1, not 0
  • Let me trace again:
    • After iteration 1: sum = 0, prefixSum[0] = 2 (initial 0 + this 0)
    • Subarray ending at index 1 with sum 0: [1,-1] (from prefixSum[0] at start)
    • After iteration 2: sum = 0, prefixSum[0] = 3
    • Subarrays ending at index 2 with sum 0:
      • [1,-1,0] (from initial prefixSum[0])
      • [-1,0] (from prefixSum[0] at index 1) - Wait, this doesn’t work
  • Actually, the correct subarrays are:
    • [1,-1] (indices 0-1): sum = 0
    • [1,-1,0] (indices 0-2): sum = 0
    • [0] (indices 2-2): sum = 0 - but this comes from prefixSum[0] at index 1
  • Let me reconsider: When we have prefixSum = 0 at index 1, we can form subarray from index 0 to 1: [1,-1]
  • When we have prefixSum = 0 at index 2, we can form:
    • Subarray from index 0 to 2: [1,-1,0] (using initial prefixSum[0])
    • Subarray from index 2 to 2: [0] (using prefixSum[0] at index 1)
  • So total = 3 ✓

Output: 3 ✓

Another Edge Case: nums = [1,1,1,1], k = 2

Initial: cnt = 0, sum = 0, prefixSum = {0: 1}

Iteration 0 (num = 1):
  sum = 0 + 1 = 1
  prefixSum.contains(1 - 2 = -1)? No ✗
  prefixSum[1] = 1
  State: cnt=0, sum=1, prefixSum={0:1, 1:1}

Iteration 1 (num = 1):
  sum = 1 + 1 = 2
  prefixSum.contains(2 - 2 = 0)? Yes ✓ (count=1)
  cnt = 0 + 1 = 1
  prefixSum[2] = 1
  State: cnt=1, sum=2, prefixSum={0:1, 1:1, 2:1}

Iteration 2 (num = 1):
  sum = 2 + 1 = 3
  prefixSum.contains(3 - 2 = 1)? Yes ✓ (count=1)
  cnt = 1 + 1 = 2
  prefixSum[3] = 1
  State: cnt=2, sum=3, prefixSum={0:1, 1:1, 2:1, 3:1}

Iteration 3 (num = 1):
  sum = 3 + 1 = 4
  prefixSum.contains(4 - 2 = 2)? Yes ✓ (count=1)
  cnt = 2 + 1 = 3
  prefixSum[4] = 1
  State: cnt=3, sum=4, prefixSum={0:1, 1:1, 2:1, 3:1, 4:1}

Return: cnt = 3 ✓

Verification:

  • Subarray [1,1] (indices 0-1): sum = 2 ✓
  • Subarray [1,1] (indices 1-2): sum = 2 ✓
  • Subarray [1,1] (indices 2-3): sum = 2 ✓
  • Total count = 3 ✓

Output: 3 ✓

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(n) - Hash map can store up to n distinct prefix sums

Key Insights

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
  2. Hash Map Counting: Count occurrences of each prefix sum to handle multiple subarrays with the same sum
  3. Initial State: Initialize with prefixSum[0] = 1 to handle subarrays starting from index 0
  4. Overlapping Subarrays: The algorithm correctly counts all overlapping subarrays that sum to k
  5. Zero Sum Handling: When k = 0, the algorithm correctly handles cases where prefix sums repeat

Comparison with LC 325

Problem Goal Hash Map Value Key Difference
LC 325 Maximum length First occurrence index Tracks maximum length
LC 560 Count subarrays Count of occurrences Counts all subarrays