Subarrays with sum K

Problem Description

Given an unsorted array of integers, find the number of continuous subarrays whose sum is exactly equal to a given number k.

Example:

• Input: arr = [10, 2, -2, -20, 10], k = -10
• Output: 3
• Explanation: The subarrays are:
  • arr[0...3]: 10 + 2 + (-2) + (-20) = -10
  • arr[1...4]: 2 + (-2) + (-20) + 10 = -10
  • arr[3...4]: -20 + 10 = -10

Solution Code

import java.util.HashMap;

class Solution {
    public int countSubarrays(int arr[], int k) {
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>(); // To store prefix sums and their frequencies
        prefixSumMap.put(0, 1); // Initialize with prefix sum 0 occurring once
        int prefixSum = 0; // To store the running prefix sum
        int count = 0; // To store the count of subarrays with sum k

        for (int num : arr) {
            prefixSum += num; // Update the running prefix sum

            // If (prefixSum - k) exists in the map, it means there are subarrays ending at the current index with sum k
            if (prefixSumMap.containsKey(prefixSum - k)) {
                count += prefixSumMap.get(prefixSum - k);
            }

            // Update the frequency of the current prefix sum in the map
            prefixSumMap.put(prefixSum, prefixSumMap.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }
}

Hint

• Use a hash map to store the frequency of prefix sums. This helps in efficiently finding the number of subarrays that sum to k.

Approach Name

Prefix Sum with Hash Map

Intuition

The idea is to use the concept of prefix sums to determine the number of subarrays that sum to k. By maintaining a running prefix sum and storing the frequency of each prefix sum in a hash map, we can efficiently check if a subarray with sum k exists.

Algorithm

1. Initialize a hash map to store prefix sums and their frequencies. Start by putting (0, 1) in the map to handle the case where the subarray starts from the beginning.
2. Initialize prefixSum to 0 and count to 0.
3. Iterate through the array:
   • Update the prefixSum by adding the current element.
   • If (prefixSum - k) exists in the map, increment the count by the frequency of (prefixSum - k).
   • Update the frequency of the current prefixSum in the map.
4. Return the count of subarrays with sum k.

Test Input

-10, 10 2 -2 -20 10

Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once, and each lookup/insert operation in the hash map takes O(1) on average.
• Space Complexity: O(n), as the hash map can store up to n prefix sums in the worst case.

This solution efficiently counts the number of subarrays with sum k using the prefix sum approach and a hash map, ensuring optimal performance for the given constraints.