Crushing Subarray Sum Equals K 🧮💥

Youssef Shaker — Mon, 18 Nov 2024 09:12:57 +0000

The Problem: What’s the Buzz About?

You’re tasked with finding how many continuous subarrays in an array sum up to a given number k. Think of it like you’re on a hunt for subarrays that add up to a specific score. Here’s the official problem: Subarray Sum Equals K on LeetCode.

The Quick Take: What’s the Deal?

Given an array of numbers and a target sum k, we need to count how many subarrays sum up exactly to k. Simple, right? Well, not so much when you start thinking about those nested loops… yikes! Let’s avoid O(n^2) solutions and hit that sweet O(n) mark with a neat trick.

A Simple Breakdown 🛠️

Here’s the plan:

We use a dictionary (hash map) to store prefix sums — these are sums of all elements from the start up to a given index.
For each element in the array, we calculate the running sum (current_sum).
If current_sum - k exists in our dictionary, it means we found a subarray that sums up to k (cue confetti 🎉).
We add current_sum to the dictionary and keep track of how many times it appears.

Why This Works

The current_sum - k trick tells us that there’s a subarray that ends at the current index with a total sum of k. This avoids recalculating every subarray sum from scratch — saving time and making our approach much more efficient.

Code Magic ✨

Here’s the Python code for the solution:
python

def subarraySum(self, nums: List[int], k: int) -> int:
    count = 0
    prefix_sum = 0
    prefix_count = {0:1}

    for num in nums:
        prefix_sum += num
        rem_sum = prefix_sum - k
        rem_sum_count = prefix_count.get(rem_sum, None)

        # if remaining sum exists in the map, 
        # add the prefix sum count
        if rem_sum_count:
            count += rem_sum_count

        # add or increment the prefix sum count
        if prefix_count.get(prefix_sum, None):
            prefix_count[prefix_sum] += 1
        else:
            prefix_count[prefix_sum] = 1

    return count

How It Flows 📈

We loop through the array, adding each number to current_sum. Check if current_sum - k exists in prefix_sum_counts. If yes, we found a subarray that sums up to k, so we update count. Record the current_sum in the dictionary.

Why I Loved Solving This

It’s one of those problems that makes you think, “There’s gotta be a trick to this!” Once you understand how prefix sums can work like a charm, it’s a satisfying ‘aha!’ moment. It’s like finding that hidden pathway in a game that saves you hours of grinding. 🕹️

Wrapping Up 🌯

This problem is a solid test of your data structure skills. You learn how to make a seemingly complex problem much more manageable using a simple map and some math magic. Plus, it’s a sweet example of how thinking outside the nested-loop box pays off!

Try it out, and you’ll soon be saying, “Subarray sum equals k? Easy peasy!” 😎

DEV Community: Youssef Shaker