HASHP03 - Editorial

editorial
, , ,
1

Problem Link - Subarray Sum equals k in Hashing

Problem Statement:

Given an array nums of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals k.

Approach 1: Brute Force

In this approach, we consider every possible subarray of the given array nums, compute the sum of elements for each subarray, and check if the sum is equal to k. If it matches, we increment the count of valid subarrays.

Complexity:

  • Time Complexity: O(N^3) Finding all subarrays takes O(N^2) Summing the elements of each subarray takes O(N).
  • Space Complexity: O(1) No additional space used.

Approach 2: Cumulative sum and Hash Map

The problem is solved using a Prefix Sum and Hash Map (or unordered_map in C++). The idea is to use the prefix sum technique to track subarray sums efficiently.

Detailed Explanation

1. Prefix Sum:

  • The prefix sum up to an index i is the sum of all elements from the start of the array to i. It helps quickly calculate subarray sums.

2. Key Insight:

  • If the sum of a subarray from index i to j is k, then:
    sum[0…j]−sum[0…(i−1)]=k
  • This means if the current prefix sum minus k exists in our map, there’s a subarray summing to k between those indices.

3. Using a Map:

  • Use an unordered map to store prefix sums and their frequencies.
  • For each new prefix sum, check if sum - k exists in the map. If so, it means a subarray with sum k ends at the current index.

Complexity:

  • Time Complexity: O(N) We traverse the array once and use the hash map for constant-time lookups and updates.
  • Space Complexity: O(N) The hash map stores prefix sums. In the worst case, all prefix sums could be unique, so the hash map could contain N entries.