2

Subarray With Given Sum

Difficulty: MEDIUM
Contributed By
Dhruv Sharma
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

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
Sample Input 1 :
2
4 5
1 3 2 4
8 9
1 2 3 4 0 4 5 0
Sample Output 1 :
Correct
Correct
Explanation Of the Sample Input 1 :
In the second test case, the elements of the array which make the sum as required are [(2,3,4), (4,5), (2,3,4,0), (4,5,0)] that are continuous. So subarray [2, 3, 4] is returned which is one of the possible subarrays which is why the required output obtained is 'Correct'.
Sample Input 2 :
2
4 4
1 2 3 4
5 0
1 2 3 4 5
Sample Output 2 :
Correct
-1 -1
Explanation Of the Sample Input 2 :
In the first test case, the possible subarrays are [ [1, 2] , [3] ] . So subarray [3] is returned which is one of the possible subarrays which is why the required output obtained is 'Correct'.

In the second test case, the elements of the array which make the sum as required are not formed by taking any elements as it is even less than the smallest element of the array. Therefore the output here is -1 -1.
Reset Code
Full screen
copy-code
Console