DSA | Day 23 of Google Interview Preparation Journey | Challenge 25: Subarray Sum Equals K

Today’s challenge was the Subarray Sum Equals K problem(#560 on LeetCode), a fascinating medium-level question that involves finding subarrays with a given sum. This problem tests problem-solving skills in array manipulation and hash maps.

Problem Statement

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

Approaches

Brute Force Approach:

• Iterate over all possible subarrays and calculate their sums.
• This approach is straightforward but has a time complexity of O(n²), which is inefficient for large inputs.

Optimized Approach with Hash Maps:

• Use a hash map to store the cumulative sums encountered so far.
• For each element in the array, calculate the cumulative sum and check if (current_sum - k) exists in the hash map.
• If it exists, it means there’s a subarray ending at the current index that sums to k.

Implementation

Here’s the Python implementation using the optimized hash map approach:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        current_sum = 0
        prefix_sums = {0: 1}
        
        for num in nums:
            current_sum += num
            if current_sum - k in prefix_sums:
                count += prefix_sums[current_sum - k]
            prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
        
        return count

Key Takeaways

• Using a hash map significantly reduces the time complexity to O(n)O(n) by efficiently tracking cumulative sums.
• This approach is ideal for large inputs and is a practical example of leveraging hash maps for optimization.

Example Walkthrough

Input:

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

Process:

• Cumulative sums: [1, 2, 3]
• Subarrays summing to k: [1, 1] (twice).

Output:

2

Input:

nums = [1, 2, 3], k = 3

Process:

• Cumulative sums: [1, 3, 6]
• Subarrays summing to k: [3], [1, 2].

Output:

2

Real-World Applications

• Financial Analysis: Identifying specific patterns in financial transactions.
• Data Analytics: Detecting trends or patterns in sequential data.

Check out the full solution and explanation here:
GitHub Repository: Link to GitHub Repository
LeetCode Submission: Link to LeetCode Submission