POTD #13 - Subarrays with sum K | Geeks For Geeks

{% raw %}

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 = -10Output: 3Explaination: 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 = 33Output: 2Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.

Input: arr = [1, 3, 5], k = 0Output: 0Explaination: 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

{% endraw %}