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:

We pick a starting point $i$ for the subarray.
We iterate through every possible ending point $j$ starting from $i$ to the end of the array.
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

Initialize a counter count = 0.
Use an outer loop with index $i$ from $0$ to $n-1$ (the start of the subarray).
Inside, maintain a variable current_sum = 0.
Use an inner loop with index $j$ from $i$ to $n-1$ (the end of the subarray).
Add nums[j] to current_sum.
If current_sum == k, increment count.
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.

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$
The Rearrangement: If we move $\text{PrefixSum}_{i-1}$ to the other side, we get: $\text{PrefixSum}_j - k = \text{PrefixSum}_{i-1}$
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

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: 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 ============================================================

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; } };

Problem Statement

Brute Force:

Intuition

Algorithm

Optimal approach

The Hash Map Strategy

The Algorithm

1. Time Complexity: O(n)O(n)O(n)

2. Space Complexity: O(n)O(n)O(n)

Chakradhar

Problem Statement

Brute Force:

Intuition

Algorithm

Optimal approach

The Hash Map Strategy

The Algorithm

1. Time Complexity: O(n)O(n)O(n)

2. Space Complexity: O(n)O(n)O(n)

1. Time Complexity: $O(n)$

2. Space Complexity: $O(n)$

1. Time Complexity: $O(n)$

2. Space Complexity: $O(n)$