Given an array arr[] of size N, and integer K. The task is to find the longest subarray with the difference between adjacent elements as K.
Examples:
Input: arr[] = { 5, 5, 5, 10, 8, 6, 12, 13 }, K =1
Output: {12, 13}
Explanation: This is the longest subarray with difference between adjacents as 1.Input: arr[] = {4, 6, 8, 9, 8, 12, 14, 17, 15}, K = 2
Output: {4, 6, 8}
Approach: Starting from the first element of the array, find the first valid sub-array and store its length and starting point. Then starting from the next element (the first element that wasn’t included in the first sub-array), find another valid sub-array and keep on updating the maximum length and start point. Repeat the process until all the valid sub-arrays have been found then print the maximum length 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// sub-array such that the// absolute difference between every two// consecutive elements is Kvoid getMaxLengthSubarray(int arr[], int N, int K){ int l = N; int i = 0, maxlen = 0; int max_len_start, max_len_end; while (i < l) { int j = i; while (i + 1 < l && (abs(arr[i] - arr[i + 1]) == K)) { i++; } // Length of the valid sub-array // currently under consideration int currLen = i - j + 1; // Update the maximum length subarray if (maxlen < currLen) { maxlen = currLen; max_len_start = j; max_len_end = i; } if (j == i) i++; } // Print the maximum length subarray for (int p = max_len_start; p <= max_len_end; p++) cout << arr[p] << " ";}// Driver codeint main(){ int arr[] = { 4, 6, 8, 9, 8, 12, 14, 17, 15 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); getMaxLengthSubarray(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{// Function to return the maximum length// sub-array such that the// absolute difference between every two// consecutive elements is Kstatic void getMaxLengthSubarray(int arr[], int N, int K){ int l = N; int i = 0, maxlen = 0; int max_len_start = 0, max_len_end = 0; while (i < l) { int j = i; while (i + 1 < l && (Math.abs(arr[i] - arr[i + 1]) == K)) { i++; } // Length of the valid sub-array // currently under consideration int currLen = i - j + 1; // Update the maximum length subarray if (maxlen < currLen) { maxlen = currLen; max_len_start = j; max_len_end = i; } if (j == i) i++; } // Print the maximum length subarray for (int p = max_len_start; p <= max_len_end; p++) System.out.print(arr[p] + " ");}// Driver codepublic static void main(String args[]){ int arr[] = { 4, 6, 8, 9, 8, 12, 14, 17, 15 }; int K = 2; int N = arr.length; getMaxLengthSubarray(arr, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program to implement# the above approach# Function to return the maximum length# sub-array such that the# absolute difference between every two# consecutive elements is Kdef getMaxLengthSubarray(arr, N, K) : l = N i = 0 maxlen = 0 while (i < l) : j = i while (i + 1 < l and (abs(arr[i] - arr[i + 1]) == K)) : i += 1 # Length of the valid sub-array # currently under consideration currLen = i - j + 1 # Update the maximum length subarray if (maxlen < currLen) : maxlen = currLen max_len_start = j max_len_end = i if (j == i) : i += 1 # Print the maximum length subarray for p in range(max_len_start, max_len_end+1, 1) : print(arr[p], end=" ")# Driver codearr = [ 4, 6, 8, 9, 8, 12, 14, 17, 15 ]K = 2N = len(arr)getMaxLengthSubarray(arr, N, K)# This code is contributed by avijitmondal1998 |
C#
// C# program for the above approachusing System;class GFG{// Function to return the maximum length// sub-array such that the// absolute difference between every two// consecutive elements is Kstatic void getMaxLengthSubarray(int []arr, int N, int K){ int l = N; int i = 0, maxlen = 0; int max_len_start = 0, max_len_end = 0; while (i < l) { int j = i; while (i + 1 < l && (Math.Abs(arr[i] - arr[i + 1]) == K)) { i++; } // Length of the valid sub-array // currently under consideration int currLen = i - j + 1; // Update the maximum length subarray if (maxlen < currLen) { maxlen = currLen; max_len_start = j; max_len_end = i; } if (j == i) i++; } // Print the maximum length subarray for (int p = max_len_start; p <= max_len_end; p++) Console.Write(arr[p] + " ");}// Driver codepublic static void Main(){ int []arr = { 4, 6, 8, 9, 8, 12, 14, 17, 15 }; int K = 2; int N = arr.Length; getMaxLengthSubarray(arr, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to return the maximum length // sub-array such that the // absolute difference between every two // consecutive elements is K function getMaxLengthSubarray(arr, N, K) { let l = N; let i = 0, maxlen = 0; let max_len_start, max_len_end; while (i < l) { let j = i; while (i + 1 < l && (Math.abs(arr[i] - arr[i + 1]) == K)) { i++; } // Length of the valid sub-array // currently under consideration let currLen = i - j + 1; // Update the maximum length subarray if (maxlen < currLen) { maxlen = currLen; max_len_start = j; max_len_end = i; } if (j == i) i++; } // Print the maximum length subarray for (let p = max_len_start; p <= max_len_end; p++) document.write(arr[p] + " "); } // Driver code let arr = [4, 6, 8, 9, 8, 12, 14, 17, 15]; let K = 2; let N = arr.length; getMaxLengthSubarray(arr, N, K); // This code is contributed by Potta Lokesh </script> |
Output
4 6 8
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
