Subarrays with sum K

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Count subarrays with sum equal to k. Prefix sum + hashmap: count of prefix sums seen so far.

Algorithm

1Map {0:1}. running_sum=0, count=0.
2For each num: running_sum += num. count += map[running_sum-k]. map[running_sum]++.

Common Pitfalls

•Works for negative numbers too. Initialize map with {0:1} for subarrays starting at index 0.

Subarrays with sum K.java

Java

// Approach: Prefix sum HashMap. For each prefix sum, check how many prior prefix sums equal (prefixSum - k).
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int countSubarrays(int arr[], int k) {
        HashMap<Integer, Integer> mp = new HashMap<>();
        int res = 0;
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (sum == k)
                res++;

            if (mp.containsKey(sum - k))
                res += mp.get(sum - k);

            mp.put(sum, mp.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

Was this solution helpful?