Subarray range with given sum

Given an unsorted array of integers arr[], and a target tar, determine the number of subarrays whose elements sum up to the target value.

Examples:

Input: arr[] = [10, 2, -2, -20, 10] , tar = -10
Output: 3
Explanation: Subarrays with sum -10 are: [10, 2, -2, -20], [2, -2, -20, 10] and [-20, 10].

Input: arr[] = [1, 4, 20, 3, 10, 5] , tar = 33
Output: 1
Explanation: Subarray with sum 33 is: [20,3,10].

Expected Time Complexity: O(n)
Expected Auxilary Space: O(n)

Constraints:
1 <= arr.size() <= 10⁶
-10⁵ <= arr[i] <= 10⁵
-10⁵ <= tar <= 10⁵

Approach 01

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // Function to count the number of subarrays which add up to the given target.
    int subArraySum(vector<int>& numbers, int targetSum) {
        unordered_map<int, int> prefixSumMap;
        int currentSum = 0, subarrayCount = 0;
        prefixSumMap[0] = 1;  // Initialize for subarrays starting from the first element.

        for (int num : numbers) {
            currentSum += num;
            int requiredPrefixSum = currentSum - targetSum;

            if (prefixSumMap.find(requiredPrefixSum) != prefixSumMap.end()) {
                subarrayCount += prefixSumMap[requiredPrefixSum];
            }

            prefixSumMap[currentSum]++;
        }
        return subarrayCount;
    }
};

class Solution:
    def subArraySum(self, numbers, targetSum):
        prefixSumMap = {0: 1}
        currentSum = 0
        subarrayCount = 0

        for num in numbers:
            currentSum += num
            requiredPrefixSum = currentSum - targetSum

            if requiredPrefixSum in prefixSumMap:
                subarrayCount += prefixSumMap[requiredPrefixSum]

            prefixSumMap[currentSum] = prefixSumMap.get(currentSum, 0) + 1

        return subarrayCount

Time Complexity

• Single pass through the array:

  The algorithm iterates through the array of n elements exactly once. For each element, we perform constant time operations like adding to the sum and checking the hash map. Therefore, the time complexity for the loop is \(O(n)\).

• Hash map operations:

  Both insertion and lookup operations in the hash map occur in constant time on average, i.e., \(O(1)\), assuming the hash map is balanced and there are no collisions.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the size of the input array.

Space Complexity

• Hash map storage:

  In the worst case, the hash map stores one entry for each unique prefix sum encountered. Thus, the space used by the hash map can grow to \(O(n)\), where n is the number of elements in the input array.

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for variables like currentSum and subarrayCount.

• Overall Space Complexity:

  The space complexity is \(O(n)\), where n is the size of the input array due to the hash map.