Are you stuck in the problem of Find Subarray with given sum? You are not alone. There are a lot of programmers who are finding it hard to solve this problem.
It is only because the programmers have not understood the basic concepts of the subarray. The Subarray is one of the important topics which you should know if you are working on enhancing your coding skills.
Subarray with given sum is a type of problem where you will have to find all the possible subarrays for the target sum from the given array.
To get all the information in the same place, then keep on scrolling this guide till the end.
What is a subarray with a given sum problem?
You all might know about the subarray. The subarray is the continuous part that is made by using the elements of the given array.
Let us make you understand through the example.
Example-
arr = [1, 2, 3, 4, 5]
There are different subarrays that can be made from it as [1,2], [1,2,3], [1,2,3,4], etc.
The Subarray with a given sum problem is one of the coding problems based on it.
In this problem, you will have to find the target sum by finding the subarray sequence which adds up to the target sum. To make you understand, we can say that there will be a target sum given which we have to find by adding the subarrays of the given array.
Get a better detailing with the help of an example:
Example -
arr = [1, 2, 3, 4, 5, 0]
Target Sum= 5
Answer: [2,3], [5], and [5,0]. On adding the given subarray, we will get the subarray with a given sum.
Explanation: In this case, we have iterated over the array. When we were traversing, then we were checking it with our target sum. Once the target sum matches, then we have found the subarray. We were doing it till the starting index gets out of the length of the array so that we can stop the iteration.
When we were doing it, then the iteration was starting from the beginning. However, if we have traversed till the last element from the 0th index, then we will increase the starting index, once we have reached the last element.
Now, let’s see the approach and dry run for the same problem which will help you in knowing how it is working.
How To Find SubArray with given sum
First of all, we will be given a problem statement which will contain the array and target sum. After it, we have to solve it by traversing over the array and storing the sum for each iteration. Let’s see how we will do it.
Problem Statement
arr = [1, 2, 3, 4, 5, 0]
Target Sum= 5
Approach
First of all, we will start our iteration from the first index.
When we will be doing it, then we have to make sure that we are storing the current sum. It is because we will be calculating and comparing it with the target sum at the same time so that we can get the subarray.
However, we have to take care of some situations. If the current sum is greater than the target sum, then we will reset the target sum to zero. After doing this, we will again start our iteration and will be checking the target sum subarray again.
We will be doing it till either we find the target sum equals the current sum or the starting index reaches the last element for the traversal.
Dry Run
We will start our iteration from the 0th index. At this time, the current sum will be 0 and the target sum will be 5.
Now, on iterating over the first element, we will store the value which will be 1. Again, we will traverse over to the next element which is 2 and it will make the current sum = 3.
After it, we will again traverse, then we will add the next element which will make 3+3= 6 which is more than the target sum, so we will reset the current sum and increase the starting index of the subarray.
Once again we will start our iteration, so this time we will be storing value for our first iteration which will be 2. In the second iteration, we will store the next element which is 3, and on adding, it will be 5 which equals 5 of the target sum. We have found our first subarray.
However, we will continue with this iteration as there might be chances that the other elements are also available which can make the target sum. On iterating, we have got the element 4 which adds up to 9, so we will reset the current sum and again start the next iteration.
The first element which we will store is the 3. After it, the next element is 4 and by adding both, we will get 7 which is greater than the target sum. Therefore, we will reset the current sum.
Again a new iteration will be started and we will increase the starting index which will be started from the 5. The 5 is already a target sum, so we have got another subarray.
However, we will continue our iteration from the same index as there might be chances of some elements which can make the target sum. On iteration, we have got 0 and on adding it, we have got 5 which equals the target sum of 5.
Now, the starting index will be increased as we have reached the last element. This time our iteration will be 0 and we will store it. Now, after it, there is no element, thus we will stop the iteration from here.
We have got our answer for the subarray with a given sum. The same approach will be used in solving the next permutation problem, so if you are going to attempt it, then make sure that you have properly understood the concept of target sum subarray.
You can easily code this problem in whatever programming language you want. It can be Python, C, C++, or something else.
Conclusion
More and more coding practice will make you ready for different interviews.
The subarray is one of the important topics of data structure and it is asked by the recruiter in the interview.
Make sure to read this guide, if you are going to appear for the interview or solve the problem.
Comments