Longest Contiguous Subarray With Absolute Diff Bounded by a Limit

Easy
0/40
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in company
eBay

Problem statement

Given an array/list 'ARR' of integers and an integer 'LIMIT'. You are supposed to return the length of the longest subarray for which the absolute difference between the maximum and minimum element is less than or equal to the 'LIMIT'.

Note : 
An array ‘B’ is a subarray of an array ‘A’ if ‘B’ that can be obtained by deletion of, several elements(possibly none) from the start of ‘A’ and several elements(possibly none) from the end of ‘A’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. Then the 'T'  test cases follow.

The first line of each test case contains two integers separated by single space ‘N’ and 'LIMIT' denoting the number of elements in the array/list.

The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format : 
For each test case, print a single line that contains an integer that denotes the length of the longest contiguous subarray with absolute difference bounded by the 'LIMIT'.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 50
1 <= 'N' <= 10^4
0 <= 'ARR[i]' <= 10^5
0 <= 'LIMIT' <= 10^5

Where 'ARR[i]' denotes the ith elements of the given array/list.

Time Limit: 1 sec
Sample Input 1 :
2
5 2
3 6 5 4 1
4 1
7 2 5 4
Sample Output 1 :
3 
2
Explanation of Sample Input 1 :
In the first test case, the longest subarray with the absolute difference of maximum and minimum element less than or equal to 2 is [1, 3]  (described by indexes with 0 based indexing). The elements of the subarray are {6, 5, 4}. The maximum element is 6 and the minimum element is 4 and the absolute difference is 6 - 4 = 2.

In the second test case, the subarray [2, 3] is the longest subarray having the absolute difference of maximum and minimum element less than or equal to 1. The length of the subarray is 2.
Sample Input 2 :
2
5 5
1 2 3 4 5
5 0
3 5 6 2 9
Sample Output 2 :
5
1
Explanation of Sample Input 2 :
In the first test case, the subarray [0, 4] is the longest subarray having the absolute difference of maximum and minimum element less than or equal to 5. The length of the subarray is 5.

In the second test case, there are 5 subarrays present having the absolute difference of maximum and minimum element as 0. [0, 0], [1, 1], [2, 2], [3, 3], [4, 4]. The length of all those subarrays is 1.
Hint

Can you think of considering all possible subarrays?

Approaches (2)
Brute Force

The basic idea of this approach is to iterate through all the possible subarrays of the given array and choose the longest one having the absolute difference of maximum and minimum element as less than or equal to the limit.

Consider the steps as follows :

  1. Initialize a variable maxLength to zero which denotes the length of the longest subarray having the absolute difference of maximum and minimum element less than or equal to the given limit.
  2. Start traversing in the array from start to end using a variable low which denotes the lowest index of the subarray such that 0 <= low <= N - 1.
  3. For each value of the low, start iterating in a nested loop using a variable high which denotes the highest index of the subarray such that low <= high <= N - 1. And initialise two variables to store the maximum and minimum element. maxElement = INT_MIN and minElement = INT_MAX.
  4. Now, for each subarray [low, higher], update the minimum and maximum element.
    • If the absolute difference of minimum and the maximum element is less than or equal to the given limit the current subarray can be chosen.
      1. If the length of the current subarray is greater than the maximum subarray length so for then do the update as
maxLength = max(maxLength, high - low + 1).
Time Complexity

O(N ^ 2), where N is the length of the given array/list.

 

Since we are iterating through every possible subarray with two nested loops. So the overall time complexity will be O(N^2).

Space Complexity

O(1)

 

As we use only constant space.

Code Solution
(100% EXP penalty)
Longest Contiguous Subarray With Absolute Diff Bounded by a Limit
Full screen
Console