Longest subsequence such that difference of max and min is at-most K
Given an array arr[] of length N, the task is to find the length of longest subsequence such that the difference of its maximum element and minimum element is not more than an integer K.
A sequence a is a subsequence of a sequence b if ????a can be obtained from b by deletion of several (possibly, zero) elements. For example, [3,1][3,1] is a subsequence of [3,2,1][3,2,1] and [4,3,1][4,3,1], but not a subsequence of [1,3,3,7][1,3,3,7] and [3,10,4][3,10,4].
Examples:
Input: K = 3, arr[]= {1, 4, 5, 6, 9}
Output: 3
Explanation:
Largest Subarray is {4, 5, 6}Input: K = 4, arr[]= {1, 2, 3, 4, 5}
Output: 5
Explanation:
Largest Subarray is {1, 2, 3, 4, 5}
Naive approach:
- Generate all subsequences and find the minimum and maximum in the subarray.
- Calculate difference between minimum and maximum and if it is smaller or equal to K, then update answer.
Time Complexity: O(2N)
Efficient approach: The idea is to first sort the array, and then use binary search to optimize the approach.
- Sort the given array
- For every distinct element A[i] in the array find the first element A[j] such that (A[j]-A[i]) > K.
- For its implementation we use Binary search or lower_bound and update ans each time as maximum of previous ans and difference of indixes.
Below is the implementation of the above approach:
C++
// C++ program to find longest // subarray such that difference // of max and min is at-most K #include <bits/stdc++.h> using namespace std; // Function to calculate longest // subarray with above condition int findLargestSubarray( vector< int >& arr, int N, int K) { // Sort the array sort(arr.begin(), arr.end()); int value1 = arr[0], value2 = 0; int index1, index2, i, MAX; index1 = index2 = 0; i = 0, MAX = 0; // Loop which will terminate // when no further elements // can be included in the subarray while (index2 != N) { // first value such that // arr[index2] - arr[index1] > K value2 = value1 + (K + 1); // calculate its index using lower_bound index2 = lower_bound(arr.begin(), arr.end(), value2) - arr.begin(); // index2- index1 will give // the accurate length // of subarray then compare // for MAX length and store // in MAX variable MAX = max(MAX, (index2 - index1)); // change the index1 // to next greater element // than previous one // and recalculate the value1 index1 = lower_bound( arr.begin(), arr.end(), arr[index1] + 1) - arr.begin(); value1 = arr[index1]; } // finally return answer MAX return MAX; } // Driver Code int main() { int N, K; N = 18; K = 5; vector< int > arr{ 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 6, 6, 7, 7, 7, 7, 7 }; cout << findLargestSubarray(arr, N, K); return 0; } |
Java
import java.util.*; class GFG { // Function to calculate longest subarray with above condition static int findLargestSubarray( ArrayList<Integer> arr, int N, int K) { // Sort the array Collections.sort(arr); int value1 = arr.get( 0 ), value2 = 0 ; int index1, index2, i, MAX; index1 = index2 = 0 ; i = 0 ; MAX = 0 ; // Loop which will terminate when no further elements can be included in the subarray while (index2 != N) { // first value such that arr[index2] - arr[index1] > K value2 = value1 + (K + 1 ); // calculate its index using binary search index2 = Collections.binarySearch(arr, value2); // If the value is not found, then the method returns (-(insertion point) - 1) if (index2 < 0 ) { index2 = -(index2 + 1 ); } // index2- index1 will give the accurate length of subarray then compare // for MAX length and store in MAX variable MAX = Math.max(MAX, (index2 - index1)); // change the index1 to next greater element than previous one and recalculate the value1 index1 = Collections.binarySearch(arr, arr.get(index1) + 1 ); if (index1 < 0 ) { index1 = -(index1 + 1 ); } value1 = arr.get(index1); } // finally return answer MAX return MAX; } // Driver Code public static void main(String[] args) { int N, K; N = 18 ; K = 5 ; ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList( 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 6 , 6 , 7 , 7 , 7 , 7 , 7 )); System.out.println(findLargestSubarray(arr, N, K)); } } |
Python3
# Python program to find longest # subarray such that difference # of max and min is at-most K from bisect import bisect_left # Function to calculate longest # subarray with above condition def findLargestSubarray(arr, N, K): # Sort the array arr.sort() value1 = arr[ 0 ] value2 = 0 index1, index2 = 0 , 0 i, MAX = 0 , 0 # Loop which will terminate # when no further elements # can be included in the subarray while index2 ! = N: # first value such that # arr[index2] - arr[index1] > K value2 = value1 + (K + 1 ) # calculate its index using bisect_left index2 = bisect_left(arr, value2) # index2- index1 will give # the accurate length # of subarray then compare # for MAX length and store # in MAX variable MAX = max ( MAX , (index2 - index1)) # change the index1 # to next greater element # than previous one # and recalculate the value1 index1 = bisect_left(arr, arr[index1] + 1 ) value1 = arr[index1] # finally return answer MAX return MAX # Driver Code if __name__ = = '__main__' : N = 18 K = 5 arr = [ 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 6 , 6 , 7 , 7 , 7 , 7 , 7 ] print (findLargestSubarray(arr, N, K)) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { static int findLargestSubarray(List< int > arr, int N, int K) { // Sort the array arr.Sort(); int value1 = arr[0], value2 = 0; int index1, index2, i, MAX; index1 = index2 = 0; i = 0; MAX = 0; // Loop which will terminate when no further elements can be included in the subarray while (index2 != N) { // first value such that arr[index2] - arr[index1] > K value2 = value1 + (K + 1); // calculate its index using binary search index2 = arr.BinarySearch(value2); // If the value is not found, then the method returns (-(insertion point) - 1) if (index2 < 0) { index2 = -(index2 + 1); } // index2- index1 will give the accurate length of subarray then compare // for MAX length and store in MAX variable MAX = Math.Max(MAX, (index2 - index1)); // change the index1 to next greater element than previous one and recalculate the value1 index1 = arr.BinarySearch(arr[index1] + 1); if (index1 < 0) { index1 = -(index1 + 1); } value1 = arr[index1]; } // finally return answer MAX return MAX; } static void Main( string [] args) { int N, K; N = 18; K = 5; List< int > arr = new List< int >( new int [] { 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 6, 6, 7, 7, 7, 7, 7 }); Console.WriteLine(findLargestSubarray(arr, N, K)); } } //contributed by adityasharmadev01 |
Javascript
// Javascript program for the above approach function bisect_left(arr, x) { let lo = 0, hi = arr.length; while (lo < hi) { let mid = (lo + hi) >> 1; if (arr[mid] < x) { lo = mid + 1; } else { hi = mid; } } return lo; } function findLargestSubarray(arr, N, K) { // Sort the array arr.sort((a, b) => a - b); let value1 = arr[0]; let value2 = 0; let index1 = 0, index2 = 0; let MAX = 0; // Loop which will terminate // when no further elements // can be included in the subarray while (index2 != N) { // first value such that // arr[index2] - arr[index1] > K value2 = value1 + (K + 1); // calculate its index using bisect_left index2 = bisect_left(arr, value2); // index2- index1 will give // the accurate length // of subarray then compare // for MAX length and store // in MAX variable MAX = Math.max(MAX, (index2 - index1)); // change the index1 // to next greater element // than previous one // and recalculate the value1 index1 = bisect_left(arr, arr[index1] + 1); value1 = arr[index1]; } // finally return answer MAX return MAX; } // Driver Code let N = 18; let K = 5; let arr = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 6, 6, 7, 7, 7, 7, 7]; console.log(findLargestSubarray(arr, N, K)); // contributed by adityasharmadev01 |
15
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)