Problem Statement
An unsorted array nums and an integer sum k is given. Array has non- negative integers in it. Find out the continuous subarray which elements sums up to the given sum. There can be multiple such subarray with given sum, print out the first such subarray with given sum.
If the subarray with given sum is found successfully then print the starting and ending indexes of the range in which that subarray is present. And if the subarray with given sum is not present then simpley print “No subarray found”.
Constraints
- $1 <= \text{nums.length} <= 2 * 10^4$
- $-10^{3} <= \text{nums[i]} <= 10^{3}$
- $-10^{7} <= \text{k} <= 10^{7}$
Example
Input:
arr=[4,3,6,5,2,8]
sum=13Output:
Subarray with given sum is found between indexes 2 and 4Example Explanation
As you can see in the example above that an array is given with elements in it. Sum of the subarray is also given which is to be found.
So here in this example an array is given along with the subarray sum “13”. So elements 6,5,2 are those which are creating the subarray of sum 13(6+5+2). So as an output the starting and ending index of that subarray with given sum is printed.
What is the Output if We Get Multiple Such Sub-Arrays Producing the Desired Sum by Adding their Elements?
It will show the first subarray whose element sum exactly matches the input sum. In brief, we are finding a sub-array that match the respective given sum for the first time by deriving the algorithm from the above- mentioned logic.
Approach 1: Brute Force or Simple Approach
In order to find out the subarray with given sum using brute force approach, we must all identify a subarray where the total of all the elements equals the specified sum value.
Algorithm
Step-1: Ask the user for an array with “n” elements, which represent the non negative integers used in the main function. We can get the user’s sum value in order to produce the result appropriately.
Step-2: Call a function to locate a subarray where the total of all of the elements equals the specified total. As an argument, pass the function the original array, its size, and the number of elements.
Step-3: Run two loops in the Subarray function, one of which will go from the array’s index 0 to its last index. To navigate the array from index 0 to index n-1, we could define i = 0 to i = n-1.
Step-4: The second loop, which we can refer to as a nested loop, would then run from j = i + 1 to n inside the first loop.
Step-5: Declare a variable called currentsum at the beginning of subarray function. Its initial value will be arr[0].
Step 6: Create a condition in the second loop to determine whether the current sum equals the specified sum or not; if it does, print the result as indexes.
Step 7: If not, determine whether the currentsum exceeds the sum of j == n, and exit the loop if it does.
Step 8: Assign currentsum to be equal to currentsum plus arr[j].
Step-9: If the test for currentsum == sum is unsuccessful,Step 8 would then calculate current sum by adding up the value that is currently present at index j to the currentsum value.
Step-10: The desired outcome will be obtained after running loop1 and the nested loop2 inside of loop1.
Step-11: If the current sum still does not match the given sum, it means that the main array does not contain such a subarray.
Step-12: When everything is finished, the desired output will appear on the screen.
Implementation
In C++
#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int arr[], int N, int sum){
int currentsum, k, l;
//picking up a starting point
for ( k= 0; k< N; k++){
currentsum = arr[k];
//try out all the subarrays which starts with i
for ( l= k+1; l < N + 1; l++){
//Return start and end index of subarray which have sum equal to given sum
if (currentsum == sum){
cout<<"Subarray with given sum is between indexes "<< k<<" and "<<l-1<<endl;
return 1;
}
else if (currentsum > sum){
break;
}
currentsum = currentsum + arr[l];
}
}
//if no such subarray found
cout<<"Subarray with given sum is NOT Found"<<endl;
return 0;
}
//Main function
int main(){
int n = 6;
int a[6] = {2, 6, 5, 31, 11, 8};
int sum = 53;
SubarraySum(a,n,sum);
return 0;
}In Java
import java.util.Scanner;
class Main{
public static int SubarraySum(int array[], int N, int sum){
int current_sum, i, j;
//picking up a starting point
for (i = 0; i < N; i++){
current_sum = array[i];
//try out all the subarrays which starts with i
for (j = i+1; j < N + 1; j++){
//Return start and end index of subarray which have sum equal to given sum
if (current_sum == sum){
System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1));
return 1;
}
else if (current_sum > sum){
break;
}
current_sum = current_sum + array[j];
}
}
//if no such subarray found
System.out.println("Subarray with given sum is NOT Found");
return 0;
}
public static void main(String[] args){
int n = 6;
int a[] = {2, 6, 5, 31, 11, 8};
int sum = 53;
SubarraySum(a,n,sum);
}
}In python
def subArraySum(arr, n, sum_):
curr_sum = arr[0]
start = 0
i = 1
#Picking up a starting point
while i <= n:
while curr_sum > sum_ and start < i-1:
curr_sum = curr_sum - arr[start]
start += 1
#Return start and end index of subarray which have sum equal to given sum
if curr_sum == sum_:
print ("Subarray with given sum is between indexes % d and % d"%(start, i-1))
return 1
if i < n:
curr_sum = curr_sum + arr[i]
i += 1
#if no such subarray found
print ("Subarray with given sum is NOT Found")
return 0
arr = [2, 6, 5, 31, 11, 8]
n = len(arr)
sum_ = 53
subArraySum(arr, n, sum_)Input:
arr[] = {2, 6, 5, 31, 11, 8}, sum = 53Output:
Subarray with given sum is between indexes 1 and 4Complexity Analysis
Time Complexity: We can see that in order to find the sum, we must traverse the array using 2 for loops and then check the condition. The time complexity will therefore be T(n) = O(n).O(n) = O(n^2)
Space Complexity: We can see that no additional space is needed to store the variables. So the space complexity will be S(n) = O(1) i.e constant.
Approach 2: Linear Complexity or Efficient Approach (Sliding Window Technique + Two Pointers technique)
We will move on to a more effective method since we have already seen how method 1, or the brute force approach, functions. This method called the linear complexity method, is very simple to use to solve any problem and has linear complexity, as the name would imply.
Let’s use this approach to talk about the problem given above:
As we’ve already seen, in order for this problem to work, we must all locate a subarray where the sum of all of the elements corresponds to the specified sum value.
Algorithm
Step-1: Take an array with “n” elements from the user as the first step; “n” refers to non-negative integers used in the main function. Additionally, request the user’s sum value so we can generate a result appropriately.
Step-2: Call a function to locate a subarray whose total of all elements match the input sum. As an argument, provide the function with the initial array, number of elements, and the provided sum value.
Step-3: In a Subarray function, execute just one loop that goes from the array’s index 0 to its last index. To move from index 0 to last index in the array, we can specify i = 0 to i = n-1. assign the variable “begin” as well. Assign a 0 to the variable “begin” as well.
Step-4: Create a variable named as currentsum at the beginning of this subarray method. This variable would then initially be initialised with arr [0] value.
Step-5: A while loop will run inside of that loop to determine if the currentsum is larger than that of the given sum and begin is less than i – 1. If it is, then the currentsum variable will be updated as currentsum – arr[begin], and begin will then be increased as begin = begin + 1.
Step-6: Next, exit the while loop and use an if statement to determine whether the currentsum equivalent to the sum or not.
Step-7: Print the outcome as the sum of the indexes if the condition is true, starting with i – 1.
Step-8: Next, use the if statement to further verify whether or not i is less than n.
Step-9: If true, add the currentsum + arr[i] to the currentsum.
Step-10: If the currentsum still doesn’t matches the supplied sum in any cases, the main array doesn’t contain any such subarray.
Step-11: As a result, we will eventually see the desired output on the screen.
Implementation
In C++
#include <iostream>
using namespace std ;
/* The program will print the indexes if the currentsum is equal to the sum, else it will print sum will not found */
int subarray(int arr[] , int n , int sum ) {
int currentsum = arr[ 0 ] , begin = 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 && begin < i - 1) {
currentsum = currentsum - arr[ begin ] ;
begin++ ;
}
// If currentsum becomes equal to sum,
// then return true
if ( currentsum == sum ){
cout<<" Subarray with given sum is between indexes " << begin << " and " << i - 1 << endl ;
return 1 ;
}
// Add this element to currentsum
if (i < n)
currentsum = currentsum + arr[ i ] ;
}
// If we reach here, then no subarray
cout << " Subarray with given sum is NOT Found " << endl ;
return 0 ;
}
int main(){
int n = 6;
int A[6] = {2, 6, 5, 31, 11, 8};
int sum = 53;
subarray ( A , n , sum ) ;
return 0 ;
} In Java
import java.util.Scanner ;
class Main {
/* Returns true if the there is a
subarray of arr[] with a sum equal to
'sum' otherwise returns false.
Also, prints the result */
static int subarray(int arr[], int n, int sum){
int currentsum = arr[0], begin = 0, i;
// Always start with the initial index of an array
for (i = 1; i <= n; i++){
// If currentsum exceeds the sum,
// then remove the starting elements
while (currentsum > sum && begin < i - 1) {
currentsum = currentsum - arr[begin];
begin++;
}
// If currentsum becomes equal to sum,
// then return true
if (currentsum == sum) {
int p = i - 1;
System.out.println(
"Subarray with given sum is between indexes " + begin
+ " and " + p);
return 1;
}
// Add this element to currentsum
if (i < n)
currentsum = currentsum + arr[i];
}
System.out.println("Subarray with given sum is NOT Found");
return 0;
}
public static void main(String[] args){
int n = 6;
int A[] = {2, 6, 5, 31, 11, 8};
int sum = 53;
subarray( A , n , sum ) ;
}
} In Python
def subarray(arr,n,sum):
currentsum = arr[0]
begin = 0
i = 1
while i <= n:
while currentsum > sum and begin < i-1:
currentsum = currentsum - arr[begin]
begin = begin + 1
if currentsum == sum:
print ("Subarray with given sum is between indexes % d and % d"%(begin, i-1))
return 1
if i < n:
currentsum = currentsum + arr[i]
i = i + 1
print("Subarray with given sum is NOT Found")
return 0
n = 6
A = [2, 6, 5, 31, 11, 8];
sum = 53;
subarray( A , n , sum) Input:
N = 6
A[] = {2, 6, 5, 31, 11, 8}
sum = 53Output:
Subarray with given sum is between indexes 1 and 4Complexity Analysis
Time Complexity:
We can see that a single for loop is used to traverse an array while checking the condition to determine the sum. As a result, time complexity will be T(n) = O(n).
Space Complexity:
As we can see from the program that no additional space is needed needed to store the elements, so it’s space complexity will be S(n)=O(1).
Approach 3: Using HashMap
Algorithm
Step-1: Create an empty dictionary with list as the value type and initialize two variables with value zero, one of them will store the current running sum and other one will store the number of subarrays with given sum.
Step-2: Now iterate over all the elements along with their corresponding indices in the given numbers list.
Step-3: While iterating keep on adding the current element in the running sum variable. In dictionary if the key of running sum is already there then simply append that index in the value list of that key, otherwise create a new key of running sum and append that index in the list.
Step-4: Now fetch out the required sum by subracting the given sum with current running sum. After fetching that required sum find out whether that required sum is there in the dictionary or not.
Step-5: If that required sum is present there in the dictionary as a key then create a new variable and store that list of indices(at which the sum is equal to the required sum) in it.
Step-6: Now find out the number of indices which gives the required sum till current index and add that number of indices to the variable which is storing number of subarrays with given sum.
Step-7: And if required sum is equals to zero it means that current index is itself having a value equal to given sum, then simply add 1 to the variable which is storing number of subarrays with given sum.
Step-8: At last return the number of subarrays with given sum present in the given list.
Implementation
In C++
class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
unordered_map<int,vector<int>>mp;
int sum_ = 0;
int ret = 0;
vector<int>v;
for (int index = 0;index < nums.size();index++)
{
int number = nums[index];
sum_ += number;
mp[sum_].push_back(index);
int req_sum = sum_ - k;
if(mp.find(req_sum) != mp.end())
{
auto it = mp.find(req_sum);
vector<int>indices;
copy(it->second.begin(),it->second.end(),back_inserter(indices));
int last_index = lower_bound(indices.begin(),indices.end(),index) - indices.begin();
ret += last_index;
}
if (req_sum == 0) ret += 1;
}
return ret;
}
};In Java
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer,List<Integer>> sums_to_index=new HashMap<>();
int sum_=0;
int ret=0;
for(int i=0;i<nums.length;++i) {
sum_+=nums[i];
if(!sums_to_index.containsKey(sum_))
sums_to_index.put(sum_, newArrayList<Integer>());
sum_to_index.get(sum_).add(i);
int required_sum=sum_-k;
if(sums_to_index.containsKey(required_sum)) {
List<Integer> indices=sums_to_index.get(required_sum);
indices.add(i);
Collections.sort(indices);
int last_index=indices.indexOf(i);
ret+=last_index;
}
if(required_sum==0)
ret+=1;
}
return ret;
}
}In Python
def subarraySum(self, nums: List[int], k: int) -> int:
di = collections.defaultdict(lambda: [])
sum_is = 0
result_is = 0
for ind, num in enumerate(nums):
sum_is += num
di[sum_is].append(ind)
remaining_sum = sum_is - k
if (remaining_sum in di):
indices = di[remaining_sum]
last_index = bisect.bisect_left(indices, ind)
result_is += last_index
if (remaining_sum == 0):
result_is += 1
return result_isInput:
N = 6
A[] = {2, 6, 5, 31, 11, 8}
sum = 53Output:
Subarray with given sum is between indexes 1 and 4Complexity Analysis
Time Complexity:
As we are using HashMap here which makes the time complexity to be T(n) = O(nlogn).
Space Complexity:
As we can see a dictionary is being created here, so it’s space complexity will be S(n)=O(n).
Conclusion
- 2 approaches are explained for finding continuous subarray which elements sums up to the given sum. These approaches are: Brute force and sliding window + two pointers having linear complexity.
- Linear Complexity approach fits best as it have less time complexity then the first one i.e is Brute force.
- If we get multiple sub-arrays producing the desired sum by adding their elements then the first subarray whose elements sum exactly matches the input sum will be there as an output.
