Given an array of n numbers where the difference between each number and the previous one doesn’t exceed one. Find the longest contiguous subarray such that the difference between the maximum and minimum number in the range doesn’t exceed one.
Examples:
Input : {3, 3, 4, 4, 5, 6}
Output : 4
The longest subarray here is {3, 3, 4, 4}
Input : {7, 7, 7}
Output : 3
The longest subarray here is {7, 7, 7}
Input : {9, 8, 8, 9, 9, 10}
Output : 5
The longest subarray here is {9, 8, 8, 9, 9}
If the difference between the maximum and the minimum numbers in the sequence doesn’t exceed one then the sequence consisted of only one or two consecutive numbers. The idea is to traverse the array and keep track of current element and previous element in current subarray. If we find an element which is not same as current or previous, we update current and previous. We also update result if required.
Implementation:
C++
// C++ code to find longest// subarray with difference// between max and min as at-most 1.#include<bits/stdc++.h>using namespace std;int longestSubarray(int input[], int length){ int prev = -1; int current, next; int prevCount = 0, currentCount = 1; // longest constant range length int longest = 1; // first number current = input[0]; for (int i = 1; i < length; i++) { next = input[i]; // If we see same number if (next == current) { currentCount++; } // If we see different number, // but same as previous. else if (next == prev) { prevCount += currentCount; prev = current; current = next; currentCount = 1; } // If number is neither same // as previous nor as current. else { longest = max(longest, currentCount + prevCount); prev = current; prevCount = currentCount; current = next; currentCount = 1; } } return max(longest, currentCount + prevCount);}// Driver Codeint main(){ int input[] = { 5, 5, 6, 7, 6 }; int n = sizeof(input) / sizeof(int); cout << longestSubarray(input, n); return 0;}// This code is contributed// by Arnab Kundu |
Java
// Java code to find longest subarray with difference// between max and min as at-most 1.public class Demo { public static int longestSubarray(int[] input) { int prev = -1; int current, next; int prevCount = 0, currentCount = 1; // longest constant range length int longest = 1; // first number current = input[0]; for (int i = 1; i < input.length; i++) { next = input[i]; // If we see same number if (next == current) { currentCount++; } // If we see different number, but // same as previous. else if (next == prev) { prevCount += currentCount; prev = current; current = next; currentCount = 1; } // If number is neither same as previous // nor as current. else { longest = Math.max(longest, currentCount + prevCount); prev = current; prevCount = currentCount; current = next; currentCount = 1; } } return Math.max(longest, currentCount + prevCount); } public static void main(String[] args) { int[] input = { 5, 5, 6, 7, 6 }; System.out.println(longestSubarray(input)); }} |
Python 3
# Python 3 code to find longest# subarray with difference# between max and min as at-most 1.def longestSubarray(input, length): prev = -1 prevCount = 0 currentCount = 1 # longest constant range length longest = 1 # first number current = input[0] for i in range(1, length): next = input[i] # If we see same number if next == current : currentCount += 1 # If we see different number, # but same as previous. elif next == prev : prevCount += currentCount prev = current current = next currentCount = 1 # If number is neither same # as previous nor as current. else: longest = max(longest, currentCount + prevCount) prev = current prevCount = currentCount current = next currentCount = 1 return max(longest, currentCount + prevCount)# Driver Codeif __name__ == "__main__": input = [ 5, 5, 6, 7, 6 ] n = len(input) print(longestSubarray(input, n)) # This code is contributed# by ChitraNayal |
C#
// C# code to find longest // subarray with difference // between max and min as // at-most 1.using System;class GFG{public static int longestSubarray(int[] input){ int prev = -1; int current, next; int prevCount = 0, currentCount = 1; // longest constant // range length int longest = 1; // first number current = input[0]; for (int i = 1; i < input.Length; i++) { next = input[i]; // If we see same number if (next == current) { currentCount++; } // If we see different number, // but same as previous. else if (next == prev) { prevCount += currentCount; prev = current; current = next; currentCount = 1; } // If number is neither // same as previous // nor as current. else { longest = Math.Max(longest, currentCount + prevCount); prev = current; prevCount = currentCount; current = next; currentCount = 1; } } return Math.Max(longest, currentCount + prevCount);}// Driver Codepublic static void Main(String[] args){ int[] input = {5, 5, 6, 7, 6}; Console.WriteLine(longestSubarray(input));}}// This code is contributed// by Kirti_Mangal |
PHP
<?php// PHP code to find longest subarray // with difference between max and // min as at-most 1.function longestSubarray($input, $length){ $prev = -1; $prevCount = 0; $currentCount = 1; // longest constant range length $longest = 1; // first number $current = $input[0]; for ($i = 1; $i < $length; $i++) { $next = $input[$i]; // If we see same number if ($next == $current) { $currentCount++; } // If we see different number, // but same as previous. else if ($next == $prev) { $prevCount += $currentCount; $prev = $current; $current = $next; $currentCount = 1; } // If number is neither same // as previous nor as current. else { $longest = max($longest, $currentCount + $prevCount); $prev = $current; $prevCount = $currentCount; $current = $next; $currentCount = 1; } } return max($longest, $currentCount + $prevCount);}// Driver Code$input = array( 5, 5, 6, 7, 6 );echo(longestSubarray($input, count($input)));// This code is contributed // by Arnab Kundu?> |
Javascript
<script>// Javascript code to find longest// subarray with difference// between max and min as at-most 1. function longestSubarray(input) { let prev = -1; let current, next; let prevCount = 0, currentCount = 1; // longest constant range length let longest = 1; // first number current = input[0]; for (let i = 1; i < input.length; i++) { next = input[i]; // If we see same number if (next == current) { currentCount++; } // If we see different number, but // same as previous. else if (next == prev) { prevCount += currentCount; prev = current; current = next; currentCount = 1; } // If number is neither same as previous // nor as current. else { longest = Math.max(longest, currentCount + prevCount); prev = current; prevCount = currentCount; current = next; currentCount = 1; } } return Math.max(longest, currentCount + prevCount); } let input=[5, 5, 6, 7, 6]; document.write(longestSubarray(input)); // This code is contributed by avanitrachhadiya2155</script> |
Output
3
Time Complexity: O(n) where n is the length of the input array.
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!
