Count Subarrays with Given Sum

95.5k
0

Given an integer array nums and an integer target, return the total number of non-empty contiguous subarrays whose sum equals target.

Return 0 when no valid subarray exists or when nums is empty.

Example 1

Input: nums = [1, 2, 3], target = 3

Output: 2

Explanation: The subarrays [1, 2] and [3] have sum 3.

Example 2

Input: nums = [1, 1, 1], target = 2

Output: 2

Explanation: The subarrays [1, 1] from index 0 to 1 and [1, 1] from index 1 to 2 have sum 2.

Brute Force Approach

The most direct approach generates every possible contiguous subarray and calculates the complete sum of each selected range.

Every pair of starting and ending indices identifies one valid subarray. Complete examination guarantees the correct count, but overlapping ranges repeatedly add many of the same elements.

Algorithm

  • Store the array size in n. If n == 0, return 0 because no non-empty subarray can be formed.

  • Initialize count with 0, where it stores the number of subarrays found whose sum is exactly target.

  • Treat every index start as the beginning of a possible subarray and every index end from start to n - 1 as its ending position.

  • For each selected range [start, end], initialize currentSum with 0 and add all elements from start through end to calculate that subarray's complete sum.

  • If currentSum == target, increment count because the selected range forms one valid subarray.

  • Return count after every possible contiguous subarray has been examined.

Dry Run

Count Subarray with Given Sum Brute Force Dry Run .png

Count Subarray with Given Sum Brute Force Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long subarraySum(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) {
return 0;
}
long long count = 0;
/*
* Generate every possible subarray
* using its start and end indices.
*/
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
long long currentSum = 0;
// Calculate the complete sum of this range.
for (int index = start; index <= end; index++) {
currentSum += nums[index];
}
// This range is valid when its sum equals target.
if (currentSum == target) {
count++;
}
}
}
return count;
}
};
int main() {
vector<int> nums = {1, 2, 1, 2};
int target = 3;
Solution solution;
cout << solution.subarraySum(nums, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Two loops select the starting and ending indices, while a third traversal calculates the sum of every selected range.

Space Complexity: O(1), because only loop indices, currentSum, and count require auxiliary storage.

Better Approach

The Brute Force Approach calculates every selected range sum from the beginning.

For a fixed starting index, the next subarray contains the previous range plus one additional ending element. Maintaining a running sum removes the third traversal and avoids repeated additions.

Algorithm

  • Store the array size in n. If the array is empty, return 0.

  • Initialize count with 0 to keep track of how many subarrays have a sum equal to target.

  • Treat every index start as the beginning of a new group of subarrays and initialize currentSum with 0 for that starting position.

  • Move end from start to n - 1 and add nums[end] to currentSum. This extends the previous range by one element instead of recalculating its complete sum.

  • Increment count whenever currentSum == target. Continue extending even when the sum becomes greater than target, because later negative values may reduce it again.

  • Return count after all starting and ending positions have been processed.

Dry Run

Count Subarray with Given Sum Better Appraoch Dry Run .png

Count Subarray with Given Sum Better Appraoch Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long subarraySum(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) {
return 0;
}
long long count = 0;
for (int start = 0; start < n; start++) {
long long currentSum = 0;
/*
* Extend the current range one element
* at a time and reuse its previous sum.
*/
for (int end = start; end < n; end++) {
currentSum += nums[end];
// Count every subarray whose sum equals target.
if (currentSum == target) {
count++;
}
}
}
return count;
}
};
int main() {
vector<int> nums = {1, 2, 1, 2};
int target = 3;
Solution solution;
cout << solution.subarraySum(nums, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every starting index extends through all possible ending indices, while each extension requires one addition.

Space Complexity: O(1), because only loop indices, currentSum, and count require auxiliary storage.

Optimal Approach

A prefix sum stores the total of all elements from the beginning of the array through the current index.

Suppose the current running sum is prefixSum. A subarray ending at the current index has sum target when an earlier prefix sum equals:

prefixSum - target

The same prefix sum may occur several times. Every occurrence represents a different valid starting position, so the frequency of each prefix sum must be stored.

Algorithm

  • Create a hash map prefixCount and store {0: 1}. This initial entry represents the empty prefix before index 0, allowing subarrays that begin at index 0 to be counted.

  • Initialize prefixSum with 0 to store the running sum and count with 0 to store the total number of valid subarrays.

  • Traverse the array from left to right and add the current element to prefixSum.

  • Calculate neededSum = prefixSum - target. Every earlier occurrence of neededSum represents a subarray ending at the current index whose sum is exactly target.

  • Add the frequency of neededSum to count, since each occurrence represents a different starting position. Then increase the frequency of prefixSum so it becomes available for future indices.

  • Return count after the complete array has been processed. If the array is empty, the loop does not execute and the result naturally remains 0.

Dry Run

Count Subarray with Given Sum Optimal Appraoch Dry Run .png

Count Subarray with Given Sum Optimal Appraoch Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long subarraySum(vector<int>& nums, int target) {
unordered_map<long long, long long> prefixCount;
/*
* The empty prefix allows subarrays
* starting from index 0 to be counted.
*/
prefixCount[0] = 1;
long long prefixSum = 0;
long long count = 0;
for (int value : nums) {
prefixSum += value;
long long neededSum = prefixSum - target;
/*
* Every earlier occurrence of neededSum
* creates a valid subarray ending here.
*/
if (prefixCount.find(neededSum) != prefixCount.end()) {
count += prefixCount[neededSum];
}
/*
* Store the current prefix only after
* checking all earlier prefix sums.
*/
prefixCount[prefixSum]++;
}
return count;
}
};
int main() {
vector<int> nums = {1, 2, 1, 2};
int target = 3;
Solution solution;
cout << solution.subarraySum(nums, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N represents the array size. Every element requires one hash-map lookup and one hash-map update.

Space Complexity: O(N), because the hash map may store up to N + 1 distinct prefix sums.

FAQS

Q1. Why are prefix-sum frequencies stored instead of only checking whether a prefix exists?

The same prefix sum may occur at multiple earlier positions. Every occurrence creates a different valid subarray ending at the current index.

Q2. Why is prefixCount initialized with {0: 1}?

The initial zero represents the empty prefix before the array starts. This allows a subarray beginning at index 0 to be counted when its sum directly equals target.

Q3. Why is the current prefix stored after checking neededSum?

Only earlier prefix sums should form a subarray ending at the current index. Storing the current prefix first could incorrectly allow the same position to act as both boundaries.

Q4. Why cannot the Better Approach stop when currentSum becomes greater than target?

Negative values may appear later and reduce the running sum. A sum greater than target can still become equal to target.

Q5. Can a sliding-window approach solve this problem?

A standard sliding window works reliably when all array values are non-negative. Negative values make the effect of expanding or shrinking the window unpredictable.

Q6. What changes when only the existence of such a subarray is required?

The frequency count is unnecessary. A set of previously seen prefix sums can determine whether at least one valid subarray exists.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

72.4k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

79.8k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

110.4k
Comments0