Count subarrays with given sum

Intuition

To find the number of subarrays with a sum equal to k, use three nested loops. The first two loops (i and j) will iterate over every possible starting and ending index of a subarray, respectively. In each iteration, the subarray range will be from index i to index j. Using a third loop, calculate the sum of the elements in the subarray [i…j], then count only those subarrays where the calculated sum equals k.

Approach

First, use a loop (i) to select every possible starting index of the subarray. The starting indices can range from index 0 to index n-1 (where n is the size of the array).
Inside this loop, run another loop (j) to signify the ending index of the subarray. For each subarray starting from index i, the possible ending indices can vary from index i to n-1.
Next, for each subarray defined by the range i to j (i.e., arr[i…j]), use another loop to calculate the sum of all the elements in that subarray.
After calculating the sum, check if the sum is equal to the given k. If it is, increase the count.

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size();
        // Number of subarrays
        int cnt = 0;

        // starting index i
        for (int i = 0; i < n; i++) {
            // ending index j
            for (int j = i; j < n; j++) {

                // calculate the sum of subarray [i...j]
                int sum = 0;
                for (int K = i; K <= j; K++)
                    sum += nums[K];

                // Increase the count if sum == k:
                if (sum == k)
                    cnt++;
            }
        }
        return cnt;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 1, 2, 4};
    int k = 6;
    // Function call to find the result
    int cnt = solution.subarraySum(nums, k);
    cout << "The number of subarrays is: " << cnt << "\n";
    return 0;
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        // Number of subarrays
        int cnt = 0;

        // starting index i
        for (int i = 0; i < n; i++) {
            // ending index j
            for (int j = i; j < n; j++) {

                // calculate the sum of subarray [i...j]
                int sum = 0;
                for (int K = i; K <= j; K++)
                    sum += nums[K];

                // Increase the count if sum == k:
                if (sum == k)
                    cnt++;
            }
        }
        return cnt;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 1, 2, 4};
        int k = 6;
        // Function call to find the result
        int cnt = solution.subarraySum(nums, k);
        System.out.println("The number of subarrays is: " + cnt);
    }
}


class Solution:
    def subarraySum(self, nums, k):
        n = len(nums)
        # Number of subarrays
        cnt = 0

        # starting index i
        for i in range(n):
            # ending index j
            for j in range(i, n):

                # calculate the sum of subarray [i...j]
                sum = 0
                for K in range(i, j + 1):
                    sum += nums[K]

                # Increase the count if sum == k:
                if sum == k:
                    cnt += 1
        return cnt

if __name__ == "__main__":
    solution = Solution()
    nums = [3, 1, 2, 4]
    k = 6
    # Function call to find the result
    cnt = solution.subarraySum(nums, k)
    print("The number of subarrays is:", cnt)

class Solution {
    subarraySum(nums, k) {
        let n = nums.length;
        // Number of subarrays
        let cnt = 0;

        // starting index i
        for (let i = 0; i < n; i++) {
            // ending index j
            for (let j = i; j < n; j++) {

                // calculate the sum of subarray [i...j]
                let sum = 0;
                for (let K = i; K <= j; K++)
                    sum += nums[K];

                // Increase the count if sum == k:
                if (sum == k)
                    cnt++;
            }
        }
        return cnt;
    }
}

const solution = new Solution();
const nums = [3, 1, 2, 4];
const k = 6;
// Function call to find the result
const cnt = solution.subarraySum(nums, k);
console.log("The number of subarrays is:", cnt);

Complexity Analysis

Time Complexity: O(N³), where N is the size of the array. We are using three nested loops here. Though all loops are not running exactly N times, the time complexity will be approximately O(N³).

Space Complexity: O(1), as we are not using any extra space.

Intuition

If we carefully observe, we can notice that to get the sum of the current subarray, the only need is to add the current element (i.e., arr[j]) to the sum of the previous subarray, arr[i…j-1]. Assume the previous subarray is arr[i…j-1] and the current subarray is arr[i…j]. The sum of arr[i…j] can be calculated as:

Sum of arr[i…j] = (sum of arr[i…j-1]) + arr[j]

This way, eliminate the third loop, and while moving the j pointer, continuously calculate the sum.

Approach

First, run a loop (i) that will select every possible starting index of the subarray. The starting indices can range from index 0 to index n-1 (where n is the array size).
Inside this loop, run another loop (j) that will signify the ending index as well as the current element of the subarray. For every subarray starting from index i, the possible ending indices can range from index i to n-1 (where n is the array size).
Within the j loop, add the current element to the sum of the previous subarray, i.e., sum = sum + arr[j].
After calculating the sum, check if the sum is equal to the given k. If it is, increment the count.

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size(); 
        // Number of subarrays
        int count = 0;

        // starting index
        for (int startIndex = 0; startIndex < n; startIndex++) { 
            int currentSum = 0;
            // ending index
            for (int endIndex = startIndex; endIndex < n; endIndex++) { 
                // calculate the sum of subarray [startIndex...endIndex]
                // sum of [startIndex..endIndex-1] + nums[endIndex]
                currentSum += nums[endIndex];

                // Increase the count if currentSum == k:
                if (currentSum == k)
                    count++;
            }
        }
        return count;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 1, 2, 4};
    int k = 6;
    // Function call to find the result
    int count = solution.subarraySum(nums, k);
    cout << "The number of subarrays is: " << count << "\n";
    return 0;
}

import java.util.*;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        // Number of subarrays
        int count = 0;

        // starting index
        for (int startIndex = 0; startIndex < n; startIndex++) {
            int currentSum = 0;
            // ending index
            for (int endIndex = startIndex; endIndex < n; endIndex++) {
                // calculate the sum of subarray [startIndex...endIndex]
                // sum of [startIndex..endIndex-1] + nums[endIndex]
                currentSum += nums[endIndex];

                // Increase the count if currentSum == k:
                if (currentSum == k)
                    count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 1, 2, 4};
        int k = 6;
        // Function call to find the result
        int count = solution.subarraySum(nums, k);
        System.out.println("The number of subarrays is: " + count);
    }
}

class Solution:
    def subarraySum(self, nums, k):
        n = len(nums)
        # Number of subarrays
        count = 0

        # starting index
        for startIndex in range(n):
            currentSum = 0
            # ending index
            for endIndex in range(startIndex, n):
                # calculate the sum of subarray [startIndex...endIndex]
                # sum of [startIndex..endIndex-1] + nums[endIndex]
                currentSum += nums[endIndex]

                # Increase the count if currentSum == k:
                if currentSum == k:
                    count += 1
        return count

if __name__ == "__main__":
    solution = Solution()
    nums = [3, 1, 2, 4]
    k = 6
    # Function call to find the result
    count = solution.subarraySum(nums, k)
    print("The number of subarrays is:", count)

class Solution {
    subarraySum(nums, k) {
        let n = nums.length;
        // Number of subarrays
        let count = 0;

        // starting index
        for (let startIndex = 0; startIndex < n; startIndex++) {
            let currentSum = 0;
            // ending index
            for (let endIndex = startIndex; endIndex < n; endIndex++) {
                // calculate the sum of subarray [startIndex...endIndex]
                // sum of [startIndex..endIndex-1] + nums[endIndex]
                currentSum += nums[endIndex];

                // Increase the count if currentSum == k:
                if (currentSum == k)
                    count++;
            }
        }
        return count;
    }
}

const solution = new Solution();
const nums = [3, 1, 2, 4];
const k = 6;
// Function call to find the result
const count = solution.subarraySum(nums, k);
console.log("The number of subarrays is:", count);

Complexity Analysis

Time Complexity: O(N²), where N is the size of the array. We are using two nested loops here, each running for approximately N times. Therefore, the time complexity will be approximately O(N²).

Space Complexity: O(1), as we are not using any extra space to solve this problem.

Intuition

In this approach, we will use the concept of prefix sums to solve the problem. The prefix sum of a subarray ending at index i is simply the sum of all the elements up to that index.

Observation:

Assume the prefix sum of a subarray ending at index 𝑖 is 𝑥. Within this subarray, we look for another subarray ending at 𝑖 whose sum is 𝑘. If such a subarray exists, the prefix sum of the remaining part must be 𝑥−𝑘. For a subarray ending at index 𝑖 with a prefix sum 𝑥, removing the segment with a prefix sum of 𝑥−𝑘 leaves a segment whose sum is 𝑘. The number of subarrays with sum 𝑘 is equal to the number of subarrays with a prefix sum of 𝑥−𝑘.

CountSubarray

Instead of directly searching for subarrays with sum 𝑘, we track the occurrence of each prefix sum using a map. The map stores each prefix sum along with its frequency. At each index 𝑖, we check the map to find how many times subarrays with the prefix sum 𝑥−𝑘 have occurred and add this number to our answer. This process is applied for all indices from 0 to 𝑛−1, where 𝑛 is the size of the array.

Approach

First, declare a map to store the prefix sums and their counts. Initially, set the value of 0 to 1 in the map to handle cases where a subarray equals the target sum k.
Now, run a loop from index 0 to n-1 (where n is the size of the array). For each index i, we will add the current element arr[i] to the prefix sum, calculate the required prefix sum x-k, add the occurrence of the prefix sum x-k (i.e., map[x-k]) to our answer, and store the current prefix sum in the map, increasing its count by 1.
Setting the initial value of 0 to 1 in the map is crucial for handling edge cases. For example, if the array is [3, -3, 1, 1, 1] and k is 3, at index 0, the prefix sum is 3, which equals k. The prefix sum of the part to be removed should be x-k = 3-3 = 0.
Without setting the value of 0 beforehand, the map would return 0 for the key 0, meaning we wouldn't count the subarray starting from the beginning correctly. By setting the initial value of 0 to 1, ensure that such subarrays are correctly counted from the start. This adjustment ensures that any subarray starting at the beginning of the array and equalling k is not overlooked.

Dry Run

Please refer to the video for complete dry-run.

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size(); 
        unordered_map<int, int> prefixSumMap;
        int currentPrefixSum = 0, subarrayCount = 0;

       // Setting 0 in the map.
        prefixSumMap[0] = 1; 
        for (int i = 0; i < n; i++) {
            // Add current element to the prefix sum:
            currentPrefixSum += nums[i];

            /*Calculate the value to 
            remove (currentPrefixSum - k)*/
            int sumToRemove = currentPrefixSum - k;

            /* Add the number of subarrays
             with the sum to be removed*/
            subarrayCount += prefixSumMap[sumToRemove];

            /* Update the count of current
            prefix sum in the map*/
            prefixSumMap[currentPrefixSum] += 1;
        }
        return subarrayCount;
    }
};

int main()
{
    // Create an instance of solution class
    Solution solution;
    vector<int> nums = {3, 1, 2, 4};
    int k = 6;
    // Function call to get the result
    int subarrayCount = solution.subarraySum(nums, k);
    cout << "The number of subarrays is: " << subarrayCount << "\n";
    return 0;
}

import java.util.HashMap;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
        int currentPrefixSum = 0, subarrayCount = 0;

        // Setting 0 in the map.
        prefixSumMap.put(0, 1);
        for (int i = 0; i < n; i++) {
            // Add current element to the prefix sum:
            currentPrefixSum += nums[i];

            /* Calculate the value to remove
            (currentPrefixSum - k)*/
            int sumToRemove = currentPrefixSum - k;

            /* Add the number of subarrays 
            with the sum to be removed*/
            subarrayCount += prefixSumMap.getOrDefault(sumToRemove, 0);

            /*Update the count of current
            prefix sum in the map*/
            prefixSumMap.put(currentPrefixSum, prefixSumMap.getOrDefault(currentPrefixSum, 0) + 1);
        }
        return subarrayCount;
    }

    public static void main(String[] args) {
        // Create an instance of the Solution class
        Solution solution = new Solution();
        int[] nums = {3, 1, 2, 4};
        int k = 6;
        // Function call to get the result
        int subarrayCount = solution.subarraySum(nums, k);
        System.out.println("The number of subarrays is: " + subarrayCount);
    }
}

class Solution:
    def subarraySum(self, nums, k):
        n = len(nums)
        prefix_sum_map = {0: 1}
        current_prefix_sum = 0
        subarray_count = 0

        for i in range(n):
            # Add current element to the prefix sum:
            current_prefix_sum += nums[i]

            """Calculate the value to remove
           (current_prefix_sum - k)"""
            sum_to_remove = current_prefix_sum - k

            """ Add the number of subarrays 
            with the sum to be removed"""
            subarray_count += prefix_sum_map.get(sum_to_remove, 0)

            """ Update the count of  current
            prefix sum in the map"""
            prefix_sum_map[current_prefix_sum] = prefix_sum_map.get(current_prefix_sum, 0) + 1

        return subarray_count

if __name__ == "__main__":
    # Create an instance of the Solution class
    solution = Solution()
    nums = [3, 1, 2, 4]
    k = 6
    # Function call to get the result
    subarray_count = solution.subarraySum(nums, k)
    print("The number of subarrays is:", subarray_count)

class Solution {
    subarraySum(nums, k) {
        let n = nums.length;
        let prefixSumMap = new Map();
        let currentPrefixSum = 0, subarrayCount = 0;

        // Setting 0 in the map.
        prefixSumMap.set(0, 1);
        for (let i = 0; i < n; i++) {
            // Add current element to prefix sum:
            currentPrefixSum += nums[i];

            /* Calculate the value to remove
            (currentPrefixSum - k)*/
            let sumToRemove = currentPrefixSum - k;

            /* Add the number of subarrays 
            with the sum to be removed*/
            subarrayCount += prefixSumMap.get(sumToRemove) || 0;

            /* Update the count of current 
            prefix sum in the map*/
            prefixSumMap.set(currentPrefixSum, (prefixSumMap.get(currentPrefixSum) || 0) + 1);
        }
        return subarrayCount;
    }
}

const solution = new Solution();
const nums = [3, 1, 2, 4];
const k = 6;
// Function call to get the result
const subarrayCount = solution.subarraySum(nums, k);
console.log("The number of subarrays is:", subarrayCount);

Complexity Analysis

Time Complexity: O(N) or O(NxlogN) depending on the map data structure used, where N is the size of the array. For example, if we use an unordered_map in C++, the time complexity will be O(N), but if we use a map, the time complexity will be O(NxlogN). The minimum complexity is O(N) as we are using a single loop to traverse the array.

Space Complexity: O(N) as we are using a map data structure.

Problem List

Count subarrays with given sum

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts