Last Updated on September 22, 2023 by Mayank Dham
The task of finding all subarrays with a given sum is a common problem in computer science and data analysis. Subarrays are contiguous segments of an array, and the challenge lies in efficiently identifying all such segments that sum up to a specified value. This problem has applications in various fields, including array manipulation, financial analysis, and data processing. In this article, we explore different approaches to solving the problem of finding all subarrays with a given sum. We delve into techniques that leverage prefix sums, hashing, and sliding windows to efficiently identify and extract the subarrays, providing insights into their advantages and limitations.
How to Find SubArray with Given Sum:
This problem is also known as subarray sum equals k. Given an array of non-negative integers and an integer sum, find a subarray that adds to a given sum.
Note: There may be more than one subarray with sum as the given sum, print first such subarray.
Examples:
Input: arr[] = [ 1, 20, 3, 10, 5 ], sum = 33
Output:
Sum found between indexes 1 and 3Explanation:
Sum of elements between indices 1 and 3 is 20 + 3 + 10 = 33
Input:
arr[] = [1, 4, 0, 0, 3, 10, 5], sum = 7Output:
Sum found between indexes 1 and 4Explanation:
Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7
Input:
arr[] = [ 1, 4 ], sum = 0Output:
No subarray foundExplanation:
There is no subarray with 0 sum
Approach 1 to Find SubArray with Given Sum
Find subarray with given sum using Nested loop
The idea behind this approach is to consider all subarrays of the given array one by one and check the sum of every subarray.
Algorithm:
Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from j.
Follow the steps given below to implement the approach:
- Traverse the array from start to end.
- From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
- For every index in inner loop update currentSum = currentSum + arr[j]
- If the currentSum is equal to the given sum then print the subarray.
Below is the implementation of the above approach.
#include <bits/stdc++.h>
using namespace std;
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
cout << "Sum found at indexes " << i << endl;
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
cout << "Sum found between indexes "
<< i << " and " << j << endl;
return;
}
}
}
}
cout << "No subarray found";
return;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
Output:
Sum found between indexes 1 and 4Time Complexity: O(N2), Trying all subarrays from every index, used nested loop for the same
Auxiliary Space: O(1).
Approach 2 to Find SubArray With Given Sum
Find subarray with given sum using sliding window technique
The idea is simple as we know that all the elements in subarray are positive so, If a subarray has sum greater than the given sum then there is no possibility that adding elements to the current subarray will be equal to the given sum. So the Idea is to use a similar approach to a sliding window technique.
Algorithm:
Step 1: Start with an empty subarray
Step 2: add elements to the subarray until the sum is less than x( given sum ).
Step 3: If the sum is greater than x, remove elements from the start of the current subarray.
Follow the steps given below to implement the approach:
- Create two variables, start=0, currentSum = arr[0]
- Traverse the array from index 1 to end.
- Update the variable currentSum by adding current element, currentSum = currentSum + arr[i]
- If the currentSum is greater than the given sum, update the variable currentSum as currentSum = currentSum – arr[start],
and update start as, start++. - If the currentSum is equal to given sum, print the subarray and break the loop.
Below is the implementation of the above approach.
Subarray with given sum 2
#include <iostream>
using namespace std;
/* Returns true if the there is a subarray of
arr[] with a sum equal to 'sum' otherwise
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
/* Initialize currentSum as value of
first element and starting point as 0 */
int currentSum = arr[0], start = 0, i;
/* Add elements one by one to currentSum and
if the currentSum exceeds the sum,
then remove starting element */
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
cout << "Sum found between indexes " << start
<< " and " << i - 1;
return 1;
}
// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}
// If we reach here, then no subarray
cout << "No subarray found";
return 0;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
Output:
Sum found between indexes 1 and 4Time Complexity: O(N)
Auxiliary Space: O(1). Since no extra space has been taken.
Finally, we optimized our code and reduced our time complexity from O(N2) to O(N).
Conclusion
The problem of finding all subarrays with a given sum presents interesting challenges and diverse solutions. While various techniques such as prefix sums, hashing, and sliding windows offer efficient ways to tackle this problem, the choice of approach depends on the specific characteristics of the data and the desired runtime complexity. Each technique has its strengths and trade-offs, and selecting the most suitable one involves understanding the problem requirements and considering factors such as memory usage, runtime efficiency, and ease of implementation. By mastering these techniques, programmers can efficiently solve this problem and apply their knowledge to a wide range of real-world scenarios.
FAQ related to subarray with given sum
Here are some FAQs related to subarray with given sum.
Q1: What is a subarray?
A subarray is a contiguous segment of an array. For example, in the array [1, 2, 3, 4], [2, 3] is a subarray, and so is [1, 2, 3, 4].
Q2: What does it mean to find all subarrays with a given sum?
The task is to identify and list all subarrays within an array that sum up to a specified value.
Q3: Why is this problem important?
The problem has practical applications in scenarios such as financial data analysis, stock market predictions, and optimizing operations involving sequences of numbers.
Q4: What are some common approaches to solving this problem?
Approaches include using prefix sums (cumulative sums), hashing techniques, and sliding windows. Prefix sums calculate cumulative sums for each position, hashing checks for previously encountered sums, and sliding windows maintain a moving subarray with the desired sum.
Q5: What is the time complexity of these techniques?
The time complexity varies based on the chosen technique. Prefix sums and sliding windows often have linear or near-linear complexity, while hashing-based methods can achieve linear complexity on average with considerations for hash collisions.