Find Subarray

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
ShareChat

Problem statement

You are given an array ‘arr’ of size ‘N’. Your task is to find the sub-array in ‘arr’ where the difference between the maximum and minimum element of the sub-array is greater than the number of elements in the sub-array. You have to return an array consisting of start and end indices of the sub-array. If sub-array does not exists, then return [-1, -1].

Note: 
The array is 1-indexed.
For example 
You are given, ‘arr’ = [4, 3, 0, 2], here the sub-array [4, 3, 0] is the sub-array where the difference between the minimum and the maximum elements in the sub-array is 4 - 0 = 4, which is greater than the length. Hence the answer is [1, 3]. Thus, the answer is ‘YES’.
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format: 
For each test case, print ‘YES’ if the subarray returned is correct. Print ‘NO’ if the subarray is not found. 

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
2 <= N <= 10^6
0 <= arr[i] <= 10^9

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
2 <= N <= 10^6
0 <= arr[i] <= 10^9

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
4
4 3 0 2
5
1 2 3 4 5
Sample Output 1:
YES
NO
Explanation:
For the first test case, ‘arr’ = [4, 3, 0, 2], here the sub-array [4, 3, 0] is the sub-array where the difference between the minimum and the maximum elements in the sub-array is 4 - 0 = 4 which is greater than the length. Hence the answer is [1, 3]. Thus the answer is ‘YES’.

For the second test case, ‘arr’ = [1, 2, 3, 4, 5], here no subarray can be found with given conditions. Hence the answer is ‘NO’.
Sample Input 2:
2
4
1 1 1 1 
4
9 0 1 1
Sample Output 2:
NO
YES
Hint

Try the brute force approach by iterating through each sub-array.

Approaches (2)
Brute Force

In this approach, we will iterate over all the possible subarrays of the given array and find the maximum and minimum elements of the array. If the difference between the maximum and minimum elements is greater than the length, we will return the starting and ending indices of the subarray.

 

Algorithm:

  • Iterate i from 0 to n - 1
    • Iterate j from i + 1 to n
      • Set maxElement as maximum element between i and j indices
      • Set minElement as minimum element between i and j indices
      • If maxElement - minElement is greater than j - i + 1
        • Then return [i + 1, j + 1]
  • Return [-1, -1]
Time Complexity

O(N^3), Where N is the number of elements in the array.

 

We are iterating over all the subarrays of the array, which will cost O(N^2) time. For each sub-array, we will find the maximum and minimum element, which will cost O(N) time. Hence the overall time complexity is O(N^2) * O(N) = O(N^3).

Space Complexity

O(1).

 

We are not using any extra space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Find Subarray
Full screen
Console