Parottasalna

Problem Statement

Geeks For Geeks: https://www.geeksforgeeks.org/problems/subarrays-with-sum-k/1

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

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.

Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.

Input: arr = [1, 3, 5], k = 0
Output: 0
Explaination: No subarray with 0 sum.

My Approach 1 (Brute Force)

Initially i tried to solve it via bruteforce, but got timedout.

class Solution:
    def countSubarrays(self, arr, k):
        # code here
        continous_count = 0
        total_length = len(arr)
        for itr in range(total_length):
            _sum = arr[itr]
            # print("ITR", arr[itr])
            for jtr in range(itr+1, total_length):
                # print("JTR", arr[jtr])
                if _sum + arr[jtr] == k:
                    # print("SUM")
                    continous_count += 1
                _sum += arr[jtr]
        return continous_count

My Approach 2 (Optimal)

After some time, searched for an approach, then came across prefix-sum . So tried to apply the same,

class Solution:
    def countSubarrays(self, arr, k):
        n = len(arr)
        pre_sum_map = {}
        pre_sum = 0
        cnt = 0
    
        pre_sum_map[0] = 1
        for i in range(n):
            pre_sum += arr[i]
            remove = pre_sum - k
            cnt += pre_sum_map.get(remove, 0)
            pre_sum_map[pre_sum] = pre_sum_map.get(pre_sum, 0) + 1
    
        return cnt

Reference:

1. https://takeuforward.org/arrays/count-subarray-sum-equals-k/
2. https://www.youtube.com/watch?v=frf7qxiN2qU