Last Updated: 5 Nov, 2020
Subarray With Given Sum
Moderate
Asked in companies
Given an array ARR of N integers and an integer S. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to S or not. If any subarray is found, return the start and end index (0 based index) of the subarray. Otherwise, consider both the START and END indexes as -1.
Note:
If two or more such subarrays exist, return any subarray.
For Example: If the given array is [1,2,3,4] and the value of S is equal to 7. Then there are two possible subarrays having sums equal to S are [1,2,3] and [3,4].
Input Format:
The first line contains a single integer T, representing the number of test cases. Each test case consists of 2 lines as follows:
The first line of each test case contains two single space-separated integers N, and S, representing the size of the array and the required sum respectively.
The second line of each test case will contain N single space-separated integers, representing the elements in the array.
Output format :
For each test case, return any two (pair) integers representing the starting and ending index of the subarray in an array/list which sum up to the given target sum or [-1, -1] instead if there is no such pair for the given input.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
-10^14 <= S <= 10^14
-10^9 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
- In this approach, we will traverse all the subarrays and for each subarray, we will check whether the sum of the elements of the subarray matches with the given sum.
- To traverse all the subarrays we will use two nested loops.
- The outer loop will select the start index and the inner loop will fix the end index of the subarray. While incrementing the inner pointer(inner loop pointer) we will also maintain the sum of elements between the start and end pointers.
- If for any subarray the sum matches with the given sum we will return both the start and end pointers of the subarray.
The idea to approach the problem is if the prefix sum up to ith index is X, and the prefix sum up to jth index is Y and it is found that Y = X + SUM, then the required subarray is found with i as start index and j as end index.
- Make a HASH_MAP having key-value pairs, where KEY = Prefix SUM, and VALUE = INDEX of prefix sum.
- Initialize a variable CURRENT_SUM = 0.
- Traverse the array and add the current element in the variable CURRENT_SUM.
- If the value of the CURRENT_SUM equals SUM, the required subarray is found.
- If the HASH_MAP contains KEY = CURRENT_SUM - SUM, then the required subarray is found, with starting index as VALUE + 1 and ending index as i, where VALUE = HASH_MAP[KEY] .
- Update the HASH_MAP with KEY = CURRENT_SUM and VALUE = i .