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 0int 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 codeint 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 approachpublic 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 0function 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 0function 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 codelet arr = [2, 4 ];document.write(getMaxLength(arr));// This code is contributed by rag2127.</script> |
Output:
1
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
