# Longest Contiguous Subarray With Absolute Diff Bounded by a Limit

Posted: 13 Dec, 2020

Difficulty: Easy

#### 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’.
```

##### 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
```

Approach 1

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 :

- 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**. - 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.** - 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**. - 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.- If the length of the current subarray is greater than the maximum subarray length so for then do the update as

- If the absolute difference of minimum and the maximum element is less than or equal to the given

`maxLength = max(maxLength, high - low + 1).`

Approach 2

The basic idea of this approach is to use a sliding window technique to solve this task. Since we need the longest subarray for which the absolute difference of minimum and the maximum element is less than or equal to the **limit**. We can use an ordered_map to store the elements of a subarray so that we can easily query for minimum and maximum elements. Consider the steps as follows:

- Create an empty
**ordered_map**named**window**that stores the elements of the window. - Initialize two variables low and high to zero which denotes the smallest index and largest index of elements in the window. Insert the first element in the window. Also, initialize a variable
**maxLength**to one which stores the answer to the problem. - Start iterating while
**high**is less than the size of the given array.- Get the maximum and minimum element of the window and store it in two variables
**maxLength**and**minElement**respectively. - If the absolute difference between
**maxLength**and**minLength**is less than or equal to the**limit**, then update**maxLength**accordingly i.e.**maxLength = max(maxLength, high - low + 1)**. And then increment the value of**high**. Insert the current element denoted by the “high” index into the window. The logic behind this is to add the next element into the window to increase its size. - Otherwise, remove the element at index
**low**and increment the value of**low**. The logic behind this is to remove the last element from the window since the absolute difference between the minimum and the maximum element is exceeding the**limit**.

- Get the maximum and minimum element of the window and store it in two variables
- Return the “maxLength” which denotes the length of the longest subarray which is bounded by
**limit**.

SIMILAR PROBLEMS

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard

# Insertion Sort

Posted: 30 Nov, 2021

Difficulty: Easy

# Subarrays With Zero Sum

Posted: 1 Dec, 2021

Difficulty: Easy

# Find Student

Posted: 1 Dec, 2021

Difficulty: Easy

# Smaller Than Triplet Sum

Posted: 1 Dec, 2021

Difficulty: Moderate