Maximum length sub-array having absolute difference of adjacent elements either 0 or 1.

Easy
0/40
Average time to solve is 15m
5 upvotes
Asked in companies
AdobeVisaRanosys

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1

2
4
5 7 5 9
5
6 -1 0 1 2

Sample Output 1

1
4

Explanation of Sample Input 1

Test Case 1: We have A = [5, 7, 5, 9]. 
As we can clearly see that no two adjacent elements have an absolute difference of either 0 or 1. So the only sub-array can be any single element of the array. So the answer will be ‘1’.

Test Case 2: The given array is [6, -1, 0, 1, 2].
Sub-array [-1, 0, 1, 2] is the longest sub-array with absolute difference of elements  0 or 1.

Sample Input 2

2
3
9 10 11
6
-2 3 -8 0 4 5

Sample Output 2

3
2
Hint

Think of using an another array.

Approaches (2)
Dynamic Programming

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’.
Time Complexity

O(N), where N is the number of elements in the given array.

 

We have traversed the array once. Therefore complexity is of order ‘N’.

Space Complexity

O(N) , where ‘N’ is the size of array.

 

We have used extra ‘dp’ array  of size ‘N’. Therefore space complexity is of order N.

Code Solution
(100% EXP penalty)
Maximum length sub-array having absolute difference of adjacent elements either 0 or 1.
Full screen
Console