Maximum length subarray with difference between adjacent elements as either 0 or 1

0 0 5 minutes read

Given an array of n integers. The task is to find the maximum length of the sub-array such that absolute difference between all the consecutive elements of the sub-array is either 0 or 1.
Examples:

Input: arr[] = {2, 5, 6, 3, 7, 6, 5, 8}
Output: 3
{5, 6} and {7, 6, 5} are the only valid sub-arrays.
Input: arr[] = {-2, -1, 5, -1, 4, 0, 3}
Output: 2

Approach: Starting from the first element of the array, find the first valid sub-array and store it’s length then starting from the next element (the first element that wasn’t included in the first sub-array), find another valid sub-array. Repeat the process until all the valid sub-arrays have been found then print the length of the maximum sub-array.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the maximum length
// of the sub-array such that the
// absolute difference between every two
// consecutive elements is either 1 or 0
int getMaxLength(int arr[],int n)
{
    int l = n;
    int i = 0, maxlen = 0;
    while (i < l)
    {
        int j = i;
        while (i+1 < l &&
             (abs(arr[i] - arr[i + 1]) == 1 ||
             abs(arr[i] - arr[i + 1]) == 0)) 
        {
            i++;
        }
 
            // Length of the valid sub-array currently
            // under consideration
            int currLen = i - j + 1;
 
            // Update the maximum length
            if (maxlen < currLen)
                maxlen = currLen;
 
            if (j == i)
                i++;
    }
 
    // Any valid sub-array cannot be of length 1
    //maxlen = (maxlen == 1) ? 0 : maxlen;
 
    // Return the maximum possible length
    return maxlen;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaxLength(arr, n);
}
 
// This code is contributed by
// Surendra_Gangwar

Java

// Java implementation of the approach
public class GFG {
 
    // Function to return the maximum length
    // of the sub-array such that the
    // absolute difference between every two
    // consecutive elements is either 1 or 0
    public static int getMaxLength(int arr[])
    {
 
        int l = arr.length;
        int i = 0, maxlen = 0;
        while (i < l) {
            int j = i;
            while (i + 1 < l
                   && (Math.abs(arr[i] - arr[i + 1]) == 1
                       || Math.abs(arr[i] - arr[i + 1]) == 0)) {
                i++;
            }
 
            // Length of the valid sub-array currently
            // under cosideration
            int currLen = i - j + 1;
 
            // Update the maximum length
            if (maxlen < currLen)
                maxlen = currLen;
 
            if (j == i)
                i++;
        }
 
        // Any valid sub-array cannot be of length 1
        maxlen = (maxlen == 1) ? 0 : maxlen;
 
        // Return the maximum possible length
        return maxlen;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 4 };
        System.out.print(getMaxLength(arr));
    }
}

Python3

# Python3 implementation of the approach 
 
# Function to return the maximum length 
# of the sub-array such that the 
# absolute difference between every two 
# consecutive elements is either 1 or 0 
def getMaxLength(arr, n) :
     
    l = n; 
    i = 0; maxlen = 0;
     
    while (i < l) :
        j = i; 
        while (i + 1 < l and
              (abs(arr[i] - arr[i + 1]) == 1 or
               abs(arr[i] - arr[i + 1]) == 0)) :
         
            i += 1; 
         
        # Length of the valid sub-array 
        # currently under cosideration 
        currLen = i - j + 1; 
 
        # Update the maximum length 
        if (maxlen < currLen) : 
            maxlen = currLen; 
 
        if (j == i) :
            i += 1; 
     
    # Any valid sub-array cannot be of length 1 
    # maxlen = (maxlen == 1) ? 0 : maxlen; 
 
    # Return the maximum possible length 
    return maxlen; 
     
# Driver code 
if __name__ == "__main__" :
 
    arr = [ 2, 4 ]; 
    n = len(arr) 
    print(getMaxLength(arr, n)); 
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach 
using System;
 
class GFG 
{ 
 
    // Function to return the maximum length 
    // of the sub-array such that the 
    // Absolute difference between every two 
    // consecutive elements is either 1 or 0 
    public static int getMaxLength(int []arr) 
    { 
 
        int l = arr.Length; 
        int i = 0, maxlen = 0; 
        while (i < l) 
        { 
            int j = i; 
            while (i + 1 < l && 
                    (Math.Abs(arr[i] - arr[i + 1]) == 1 ||
                    Math.Abs(arr[i] - arr[i + 1]) == 0)) 
            { 
                i++; 
            } 
 
            // Length of the valid sub-array currently 
            // under consideration 
            int currLen = i - j + 1; 
 
            // Update the maximum length 
            if (maxlen < currLen) 
                maxlen = currLen; 
 
            if (j == i) 
                i++; 
        } 
 
        // Any valid sub-array cannot be of length 1 
        maxlen = (maxlen == 1) ? 0 : maxlen; 
 
        // Return the maximum possible length 
        return maxlen; 
    } 
 
    // Driver code 
    public static void Main(String []args) 
    { 
        int []arr = { 2, 4 }; 
        Console.Write(getMaxLength(arr)); 
    } 
} 
 
// This code is contributed by Arnab Kundu

PHP

<?php
// PHP implementation of the approach
 
// Function to return the maximum length
// of the sub-array such that the
// absolute difference between every two
// consecutive elements is either 1 or 0
function getMaxLength($arr, $n)
{
    $l = $n;
    $i = 0;
    $maxlen = 0;
    while ($i < $l)
    {
        $j = $i;
        while ($i + 1 < $l &&
              (abs($arr[$i] - $arr[$i + 1]) == 1 ||
                abs($arr[$i] - $arr[$i + 1]) == 0)) 
        {
            $i++;
        }
 
        // Length of the valid sub-array 
        // currently under consideration
        $currLen = $i - $j + 1;
 
        // Update the maximum length
        if ($maxlen < $currLen)
            $maxlen = $currLen;
 
        if ($j == $i)
            $i++;
    }
 
    // Any valid sub-array cannot be of length 1
    //maxlen = (maxlen == 1) ? 0 : maxlen;
 
    // Return the maximum possible length
    return $maxlen;
}
 
// Driver code
$arr = array(2, 4 );
$n = sizeof($arr);
echo getMaxLength($arr, $n)
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum length
    // of the sub-array such that the
    // absolute difference between every two
    // consecutive elements is either 1 or 0
function getMaxLength(arr)
{
    let l = arr.length;
        let i = 0, maxlen = 0;
        while (i < l) {
            let j = i;
            while (i + 1 < l
                   && (Math.abs(arr[i] - arr[i + 1]) == 1
                       || Math.abs(arr[i] - arr[i + 1]) == 0)) {
                i++;
            }
   
            // Length of the valid sub-array currently
            // under cosideration
            let currLen = i - j + 1;
   
            // Update the maximum length
            if (maxlen < currLen)
                maxlen = currLen;
   
            if (j == i)
                i++;
        }
   
        // Any valid sub-array cannot be of length 1
        //maxlen = (maxlen == 1) ? 0 : maxlen;
   
        // Return the maximum possible length
        return maxlen;
}
 
// Driver code
let arr = [2, 4 ];
document.write(getMaxLength(arr));
 
// This code is contributed by rag2127.
</script>

Output:

Time Complexity : O(n) ,where n is size of given array.

Space Complexity : O(1) ,as we are not using any extra space.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!