Last Updated: 21 Oct, 2021

Find Subarray

Moderate

Asked in company

Solve now

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.

Solve now

Approaches

01 Approach

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]

Solve now

02 Approach

In this approach, it can be proven if a subarray exists with the given conditions then, two consecutive elements in the subarray will have a difference of more than 1, and that will satisfy the given conditions.

Proof:

Let there be a subarray of the array arr, arr[l: r] from indices l and r, maxIndex and minIndex be the indices of maximum and minimum elements of the subarray and let's assume for generality that maxIndex < minIndex and the proof will also work for minIndex < maxIndex, then for the subarray, arr[l: r], the following condition will hold:

arr[maxIndex] - arr[minIndex] > r - l + 1 > minIndex - maxIndex + 1

The difference between minIndex and maxIndex should be less than the difference between the elements at the indices.

Let's add and subtract all the elements between maxIndex and minIndex in the equation- :

(arr[maxIndex] - arr[maxIndex - 1]) + (arr[maxIndex - 1] - arr[maxIndex - 2]) … + arr[minIndex + 1] - arr[minIndex] < maxIndex - minIndex + 1

It can be seen that maxIndex - minIndex + 1 will be greater than 1. So one of the consecutive pairs must be greater than 1.

Algorithm:

Iterate i from 0 to size of arr - 1
- If the absolute value of arr[i + 1] - arr[i] is greater than 1.
  - then return [ i + 1, i + 2]
Return [ -1, -1]

Solve now