🚀 Prefix Sum + Hashing Technique

🚀 Prefix Sum + Hashing Technique

The Prefix Sum + Hashing technique is a powerful approach to solving problems that involve subarrays with a specific sum condition. It helps optimize problems that would otherwise require O(N²) brute force solutions to an efficient O(N) approach using a hashmap (dictionary in Python).

---

🔹 When to Use Prefix Sum + Hashing?

✅ Finding subarrays with a given sum.
✅ Problems where we need fast lookups of previously seen prefix sums.
✅ Used frequently in range sum queries, subarrays, and constraints on sum differences.

---

🔹 Concept Behind Prefix Sum + Hashing

1️⃣ Compute the prefix sum:

• The prefix sum at index i is the sum of all elements from 0 to i.
• This helps us quickly compute subarray sums without iterating through the array multiple times.

2️⃣ Use a HashMap (Dictionary) to store prefix sums:

• The hashmap stores the prefix sum as a key and its occurrence count or index as a value.
• This allows quick lookups to check if a required sum exists.

3️⃣ Find the target sum efficiently:

• If we want a subarray sum of target, we check if (prefix_sum - target) exists in the hashmap.

---

🔹 Example: Subarray Sum Equals K (LeetCode 560)

Problem: Find the number of contiguous subarrays whose sum equals k.
💡 Optimal Solution: Use prefix sum + hashmap to track occurrences of (prefix_sum - k).

🔹 Implementation

from collections import defaultdict

def subarraySum(nums, k):
    prefix_sum = 0
    count = 0
    sum_freq = defaultdict(int)
    sum_freq[0] = 1  # To handle cases where prefix_sum itself is k

    for num in nums:
        prefix_sum += num  # Compute prefix sum

        # Check if (prefix_sum - k) exists in hashmap
        if (prefix_sum - k) in sum_freq:
            count += sum_freq[prefix_sum - k]

        # Store the current prefix sum in the hashmap
        sum_freq[prefix_sum] += 1

    return count

---

🔹 Explanation with Example

Input:

nums = [1, 2, 3, 2, -3, 1, 4]
k = 5

We track the prefix sum and use a hashmap to store counts.

Index Element Prefix Sum (Prefix Sum - k) Exists? Count Updated? HashMap (sum_freq)

0	1	1	❌ No	0	{0:1, 1:1}
1	2	3	❌ No	0	{0:1, 1:1, 3:1}
2	3	6	✅ Yes (6-5=1)	+1 (count=1)	{0:1, 1:1, 3:1, 6:1}
3	2	8	✅ Yes (8-5=3)	+1 (count=2)	{0:1, 1:1, 3:1, 6:1, 8:1}
4	-3	5	✅ Yes (5-5=0)	+1 (count=3)	{0:1, 1:1, 3:1, 6:1, 8:1, 5:1}
5	1	6	✅ Yes (6-5=1)	+1 (count=4)	{0:1, 1:1, 3:1, 6:2, 8:1, 5:1}
6	4	10	✅ Yes (10-5=5)	+1 (count=5)	{0:1, 1:1, 3:1, 6:2, 8:1, 5:1, 10:1}

✅ Final Count: 5 (5 valid subarrays with sum = 5)

---

🔹 Time & Space Complexity

• Time Complexity: O(N) (each element is processed once).
• Space Complexity: O(N) (hashmap stores at most N prefix sums).

---

🔹 Other Problems Using Prefix Sum + Hashing

Problem Description

[LeetCode 325] Maximum Size Subarray Sum Equals K	Find the longest subarray with sum = k
[LeetCode 523] Continuous Subarray Sum	Check if subarray sum is a multiple of k
[LeetCode 974] Subarray Sums Divisible by K	Count subarrays whose sum is divisible by k
[LeetCode 930] Binary Subarrays With Sum	Count subarrays with sum exactly k in a binary array

---

🔹 Summary

Concept Description

Prefix Sum	Computes cumulative sum to track subarrays efficiently
Hashing	Stores prefix sums to allow O(1) lookup
Time Complexity	O(N) using hashmap
Use Cases	Finding subarrays with sum constraints

---

🚀 Takeaways

1️⃣ Always store the prefix sum in a hashmap for quick lookups.
2️⃣ (prefix_sum - target) in hashmap → A valid subarray is found.
3️⃣ O(N) time complexity makes it much faster than brute force O(N²).

Would you like me to explain any variations of this technique? 🚀