Problem Details
Maximum length sub-array having absolute difference of adjacent elements either 0 or 1.
Last Updated: 3 Mar, 2021
Maximum length sub-array having absolute difference of adjacent elements either 0 or 1.
Easy
Asked in companies
Given an array ‘A’ of ‘N’ integers, you need to find the maximum length of the sub-array such that the absolute difference between the adjacent elements of the sub-array should be either 0 or 1.
A sub-array is a contiguous section of original elements of the array.
For Example
Let us say A = [2,4,6,7,6,9], then adjacent elements of sub array [6,7,6] have absolute difference of either 0 or 1 and this is the maximum length sub-array. So the required answer will be 3.
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test contains an integer ‘N’ - number of elements in the array.
The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.
Output Format
For each test case, print a single line containing a single integer denoting the maximum length of sub-array having an absolute difference of adjacent elements either 0 or 1.
The output of each test case will be printed in a separate line.
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
-10 ^ 8 <= A[ i ] <=10 ^ 8
Where ‘T’ is the number of test cases, ‘N’ is the number of elements in the array, A[i] is an array element at index ‘i’.
Time limit: 1 sec.
Approaches
The simple idea is we will take an array ‘dp’ and initialized its values to 1. dp[ i ] will store the maximum length of the subarray that can be obtained from array A[ 0…….i].
Now If absolute difference of A[ i ] and A [ i-1 ] is either 0 or 1 then we can say that length of sub array with absolute difference of 0 or 1 from array A[0…..i] is 1 + length of sub array obtained from array A[ 0….. i-1 ] i e dp[ i ] = dp[ i-1 ] +1.
The maximum value of ‘dp’ array will be the longest subarray with elements having absolute difference of either 0 or 1.
Algorithm:
- Take an array ‘dp’ of size ‘N’ and initialize its values to 1.
- Take a variable ‘ans’ (initialized to 0) to store the answer.
- Run a loop of i : 1 to N - 1
- If abs(A[ i ] - A[ i - 1] == 0) || abs(A[ i ] - A[ i - 1] == 1)
dp [ i ] = dp [ i -1] +1.
- Update ‘ans’ as ans = max(ans, dp[ i ] ).
- Return ‘ans’.
The key idea is to iterate through array elements. If two adjacent elements have absolute difference of either 0 or 1 then we will find the length up to which the difference of elements remains 0 or 1. Now we will repeat this process until we reach the last element of the array and print the maximum length found.
Algorithm
- Take a variable ‘idx’ (initialized to 0) to store the index of array elements, ans (initialized to 0) to store the required answer.
- Run a loop while idx < N.
- Store the value of ‘idx’ in a variable ‘temp’.(To store starting index of sub-array)
- Increment ‘idx’ until idx + 1 < N and abs( A[ idx ] - A[ idx + 1 ] == 0) or abs( A[ idx ] - A[ idx + 1 ] == 1) (Here abs means absolute value)
- Now idx - temp +1 is the length of sub-array with absolute difference of 0 or 1.
- Update ‘ans’ as ans = max (ans , idx - temp +1)
- If temp = idx, this means the absolute difference of adjacent element of A[idx] is not 0 or 1. So increment ‘idx’.
- Return ‘ans’.
Similar problems