Leetcode 560 Subarray Sum Equals K

Problem Statement

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

Example 1:

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

Example 2:

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

Constraints:

• $1 \le \text{nums.length} \le 2 \times 10^4$
• $-1000 \le \text{nums}[i] \le 1000$
• $-10^7 \le k \le 10^7$

Brute Force:

Intuition

A subarray is defined by a start index and an end index. To check every possible subarray:

1. We pick a starting point $i$ for the subarray.
2. We iterate through every possible ending point $j$ starting from $i$ to the end of the array.
3. For every range $[i, j]$, we calculate the sum of elements and check if that sum is equal to $k$.

Since we are checking all pairs $(i, j)$, there are $O(n^2)$ possible subarrays.

Algorithm

1. Initialize a counter count = 0.
2. Use an outer loop with index $i$ from $0$ to $n-1$ (the start of the subarray).
3. Inside, maintain a variable current_sum = 0.
4. Use an inner loop with index $j$ from $i$ to $n-1$ (the end of the subarray).
5. Add nums[j] to current_sum.
6. If current_sum == k, increment count.
7. Return count after all loops finish.

def subarraySum(nums, k):
    count = 0
    n = len(nums)
    
    # Outer loop for start index
    for i in range(n):
        current_sum = 0
        # Inner loop for end index
        for j in range(i, n):
            current_sum += nums[j]
            
            # Check if condition is met
            if current_sum == k:
                count += 1
                
    return count

Dry Run

============================================================
DRY RUN: Subarray Sum Equals K (Brute Force)
Input: nums = [1, 2, 3], k = 3
============================================================

[Phase 1: Starting at index 0]
  i=0, j=0: Subarray [1]       | Sum = 1
  i=0, j=1: Subarray [1, 2]    | Sum = 3  >> MATCH FOUND!
  i=0, j=2: Subarray [1, 2, 3] | Sum = 6

[Phase 2: Starting at index 1]
  i=1, j=1: Subarray [2]       | Sum = 2
  i=1, j=2: Subarray [2, 3]    | Sum = 5

[Phase 3: Starting at index 2]
  i=2, j=2: Subarray [3]       | Sum = 3  >> MATCH FOUND!

============================================================
Total Count: 2
============================================================

Complexity Analysis

• Time Complexity: $O(n^2)$ because we have nested loops iterating through the array.
• Space Complexity: $O(1)$ as we only use a few variables for counting and summing.

Optimal approach

Imagine you are walking along the array, keeping a running total called current_sum.

1. The Goal: We want to find a subarray that sums to k. Mathematically, this means:$$\text{Sum}(\text{i to j}) = \text{PrefixSum}_j - \text{PrefixSum}_{i-1} = k$$
2. The Rearrangement: If we move $\text{PrefixSum}_{i-1}$ to the other side, we get:$$\text{PrefixSum}_j - k = \text{PrefixSum}_{i-1}$$
3. The "Aha!" Moment: As we iterate through the array, at any point j, we know our current total (PrefixSum_j). We just need to check: "Have I seen a previous prefix sum that equals current_sum - k?" * If the answer is Yes, it means the elements between that previous point and the current point must sum exactly to k.

The Hash Map Strategy

Instead of using a nested loop to re-calculate sums, we use a Hash Map (Dictionary) to store every PrefixSum we encounter and how many times we have seen it.

• Key: The PrefixSum value.
• Value: How many times this PrefixSum has occurred so far.

To implement the optimal $O(n)$ solution, we use a Hash Map (or dictionary) to keep track of the prefix sums encountered so far.

The Algorithm

• Initialize Variables:
  • count = 0: To keep track of the number of valid subarrays found.
  • current_sum = 0: To store the running total of elements.
  • prefix_sums = {0: 1}: A dictionary (hash map) initialized with {0: 1}. This handles cases where a subarray starting from index 0 equals k.
• Iterate Through the Array:
  • For each element num in the array:
    • Update current_sum by adding num.
    • Check for Complement: Calculate target = current_sum - k.
    • If target exists in the prefix_sums dictionary, it means there is a subarray that sums to k. Add the frequency of target to count.
    • Update Map: Store or increment the current_sum in the prefix_sums dictionary to make it available for future lookups.
• Return:
  • After iterating through the entire array, return count.

C++ code:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        int current_sum = 0;
        unordered_map<int, int> prefix_sums;
        
        // Base case: a prefix sum of 0 has occurred once
        prefix_sums[0] = 1;
        
        for (int num : nums) {
            current_sum += num;
            
            // If (current_sum - k) exists, we found valid subarrays
            if (prefix_sums.count(current_sum - k)) {
                count += prefix_sums[current_sum - k];
            }
            
            // Record the current prefix sum in the map
            prefix_sums[current_sum]++;
        }
        
        return count;
    }
};

Dry Run:

1. Time Complexity: $O(n)$

• Single Traversal: We iterate through the array of $n$ elements exactly once.
• Constant Time Lookups: Inside the loop, we perform dictionary operations (find or count) and updates (insert or increment). In C++, unordered_map provides an average $O(1)$ time complexity for these operations.
• Total Calculation: Since we perform a constant number of $O(1)$ operations for each of the $n$ elements, the overall time complexity is $O(n) \times O(1) = O(n)$.

2. Space Complexity: $O(n)$

• Hash Map Storage: In the worst-case scenario (e.g., an array where every prefix sum is unique), we will store a new entry in the unordered_map for every element we process.
• Total Calculation: This results in a space requirement that grows linearly with the input size, leading to $O(n)$ space complexity.

problem :

Subarray Sum Equals K - LeetCode

video reference:

https://youtu.be/xvNwoz-ufXA?si=Y_PVG5Lv0CnQT-XV