Subarray range with given sum

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find number of subarrays with sum in range [lower, upper]. Prefix sum + sorted structure.

Algorithm

1Prefix sums. For each j: count i < j where prefix[j]-upper <= prefix[i] <= prefix[j]-lower. Use sorted array or BIT.

Common Pitfalls

•Same as LC 327. Merge sort or BIT to count inversions in given range. O(n log n).

Subarray range with given sum.java

Java

// Approach: Prefix sum HashMap. For each index, check if prefixSum - k exists in the map.
// Time: O(n) Space: O(n)
class Solution {
    // Function to count the number of subarrays which adds to the given sum.
    static int subArraySum(int arr[], int tar) {
        HashMap<Integer, Integer> sumFrequency = new HashMap<>();
        int cumulativeSum = 0;
        int count = 0;

        sumFrequency.put(0, 1);

        for (int num : arr) {
            cumulativeSum += num;

            if (sumFrequency.containsKey(cumulativeSum - tar))
                count += sumFrequency.get(cumulativeSum - tar);

            sumFrequency.put(cumulativeSum, sumFrequency.getOrDefault(cumulativeSum, 0) + 1);
        }

        return count;
    }
}

Was this solution helpful?