DSA Patterns: Prefix Sum with Hash Map Technique ✨✨✨

---

Welcome to the first article in our DSA Patterns series, where we discuss commonly used patterns to solve coding problems, particularly for interviews. In this blog, we will break down the Prefix Sum with Hash Map technique—a powerful approach for solving subarray-related problems efficiently. 🚀🚀🚀

We will discuss why this technique is useful, how it works, and solve a few classic problems to understand the pattern better. By the end, you will also get a generalized code template to apply this pattern to similar problems. ✅✅✅

---

Why Use Prefix Sum + Hash Map? 🧠📊🔑

Subarray-related problems often involve finding:

• The count of subarrays that satisfy a condition.

• The maximum length of a subarray meeting specific criteria.

• Checking whether a subarray exists that meets certain requirements.

Using a brute-force approach for such problems takes O(n^2) time complexity, as we need to check every possible subarray. However, by combining the Prefix Sum technique with a Hash Map, we can reduce the time complexity to O(n). ⚡⚡⚡

Why Not Sliding Window? 🤔⛔

You might be wondering why we can't use the sliding window approach here. The sliding window technique works only when the prefix sum has a monotonous nature (strictly increasing or decreasing). If the input contains negative numbers, sliding window fails.

For such cases, the Prefix Sum + Hash Map technique becomes the optimal choice. 💡💡💡

---

How Does Prefix Sum + Hash Map Work? 🛠️🔍📚

The idea is simple:

1. Compute the prefix sum up to each index.

2. Use a Hash Map to store the prefix sum as a key and its corresponding index (or count) as a value.

3. Check if the current prefix sum satisfies the given condition using values stored in the Hash Map. 🔑🔑🔑

Key Concept: 📌💡🔎

If the prefix sum up to the ith index is X and the prefix sum up to the jth index is Y (where j > i), and it is found that:

Then, the subarray between i+1 and j has a sum equal to k. ✅✅✅

The Hash Map allows us to efficiently check if such a prefix sum X already exists.

---

Key Problems and Applications 🔥🧩🛠️

We will explore three types of problems that use this pattern:

1. Count Subarrays meeting a condition.

2. Maximum Length Subarray meeting a condition.

3. Check if a Subarray Exists that satisfies a condition. 🎯🎯🎯

Each type of problem is illustrated with relevant examples.

---

1. Count Subarrays Meeting a Condition 🎯💲📝

Problem 1.1: Count Subarray Sum Equals K 🎲📏✅

Leetcode Problem 560

Condition: Find the number of subarrays where the sum equals k. Negative values are allowed in the input.

from collections import defaultdict

def count_subarray_sum(nums, k):
    prefix_sum = 0
    count = 0
    prefix_map = defaultdict(int)
    prefix_map[0] = 1  # Initialize with prefix sum 0

    for num in nums:
        prefix_sum += num  # Calculate current prefix sum
        if prefix_sum - k in prefix_map:
            count += prefix_map[prefix_sum - k]  # Check for subarray
        prefix_map[prefix_sum] += 1  # Store prefix sum in hashmap

    return count

# Example Usage
nums = [1, 1, 1]
k = 2
print(count_subarray_sum(nums, k))  # Output: 2

Dry Run 🗒📑💡

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

Explanation:

• Step 1: Prefix sum is 1. Needed sum = -1, not found in the HashMap.

• Step 2: Prefix sum becomes 2. Needed sum = 0, found in HashMap (1 subarray).

• Step 3: Prefix sum becomes 3. Needed sum = 1, found in HashMap (1 subarray).

Output: 2 subarrays meet the condition.

---

2. Maximum Length Subarray Meeting a Condition 📏🔍✨

Problem 2.1: Maximum Size Subarray Sum Equals K 🛠️📀🔑

Leetcode Premium Problem 325

Condition: Find the maximum length of a subarray whose sum equals k. Negative values are allowed.

def max_length_subarray_sum(nums, k):
    prefix_sum = 0
    max_length = 0
    prefix_map = {0: -1}  # Initialize with prefix sum 0 at index -1

    for i, num in enumerate(nums):
        prefix_sum += num  # Update prefix sum
        if prefix_sum - k in prefix_map:
            max_length = max(max_length, i - prefix_map[prefix_sum - k])
        if prefix_sum not in prefix_map:
            prefix_map[prefix_sum] = i  # Store first occurrence of prefix sum

    return max_length

# Example Usage
nums = [1, -1, 5, -2, 3]
k = 3
print(max_length_subarray_sum(nums, k))  # Output: 4

---

3. Check If a Subarray Exists with Given Condition 🔍🔎✅

Problem 3.1: Continuous Subarray Sum 📊🎯🔗

Leetcode Problem 523

Condition: Check if there exists a subarray with a sum that is a multiple of k. 🔑🔑🔑

---

Generalized Code Template for Prefix Sum + Hash Map 🛠️💜📚

Here is a general template you can adapt for solving similar problems:

from collections import defaultdict

def prefix_sum_hashmap(nums, condition_func):
    prefix_sum = 0
    result = 0
    prefix_map = defaultdict(int)
    prefix_map[0] = 1  # Initialize with prefix sum 0

    for num in nums:
        prefix_sum += num  # Update prefix sum
        # Check for condition using the prefix_map
        if condition_func(prefix_sum, prefix_map):
            result += 1  # Update result based on condition
        prefix_map[prefix_sum] += 1  # Store prefix sum

    return result

---

This template can be customized based on:

• The condition you need to check.

• Whether you need a count, a boolean check, or the maximum length of a subarray.

---

Key Takeaways

• The Prefix Sum + Hash Map technique is highly efficient for solving subarray-related problems with O(n) time complexity.

• It is especially useful when dealing with negative numbers where sliding window cannot be applied.

• By storing prefix sums in a Hash Map, you can quickly check for subarrays satisfying the required conditions.

---

Stay tuned for the next post in the DSA Patterns series, where we will explore another powerful pattern to solve Leetcode problems efficiently!

If you found this blog helpful, share it with your peers preparing for interviews. Happy coding!

---