Longest subarray not having more than K distinct elements
Given N elements and a number K, find the longest subarray which has not more than K distinct elements.(It can have less than K).
Examples:
Input : arr[] = {1, 2, 3, 4, 5} k = 6 Output : 1 2 3 4 5 Explanation: The whole array has only 5 distinct elements which is less than k, so we print the array itself. Input: arr[] = {6, 5, 1, 2, 3, 2, 1, 4, 5} k = 3 Output: 1 2 3 2 1, The output is the longest subarray with 3 distinct elements.
A naive approach will be to be traverse in the array and use hashing for every sub-arrays, and check for the longest sub-array possible with no more than K distinct elements.
An efficient approach is to use the concept of two pointers where we maintain a hash to count for occurrences of elements. We start from the beginning and keep a count of distinct elements till the number exceeds k. Once it exceeds K, we start decreasing the count of the elements in the hash from where the sub-array started and reduce our length as the sub-arrays gets decreased so the pointer moves to the right. We keep removing elements till we again get k distinct elements. We continue this process till we again have more than k distinct elements and keep the left pointer constant till then. We update our start and end according to that if the new sub-array length is more than the previous one.
Implementation:
C++
// CPP program to find longest subarray with // k or less distinct elements. #include <bits/stdc++.h> using namespace std; // function to print the longest sub-array void longest( int a[], int n, int k) { unordered_map< int , int > freq; int start = 0, end = 0, now = 0, l = 0; for ( int i = 0; i < n; i++) { // mark the element visited freq[a[i]]++; // if its visited first time, then increase // the counter of distinct elements by 1 if (freq[a[i]] == 1) now++; // When the counter of distinct elements // increases from k, then reduce it to k while (now > k) { // from the left, reduce the number of // time of visit freq[a[l]]--; // if the reduced visited time element // is not present in further segment // then decrease the count of distinct // elements if (freq[a[l]] == 0) now--; // increase the subsegment mark l++; } // check length of longest sub-segment // when greater than previous best // then change it if (i - l + 1 >= end - start + 1) end = i, start = l; } // print the longest sub-segment for ( int i = start; i <= end; i++) cout << a[i] << " " ; } // driver program to test the above function int main() { int a[] = { 6, 5, 1, 2, 3, 2, 1, 4, 5 }; int n = sizeof (a) / sizeof (a[0]); int k = 3; longest(a, n, k); return 0; } |
Java
// Java program to find longest subarray with // k or less distinct elements. import java.util.*; class GFG { // function to print the longest sub-array static void longest( int a[], int n, int k) { int [] freq = new int [ 7 ]; int start = 0 , end = 0 , now = 0 , l = 0 ; for ( int i = 0 ; i < n; i++) { // mark the element visited freq[a[i]]++; // if its visited first time, then increase // the counter of distinct elements by 1 if (freq[a[i]] == 1 ) now++; // When the counter of distinct elements // increases from k, then reduce it to k while (now > k) { // from the left, reduce the number of // time of visit freq[a[l]]--; // if the reduced visited time element // is not present in further segment // then decrease the count of distinct // elements if (freq[a[l]] == 0 ) now--; // increase the subsegment mark l++; } // check length of longest sub-segment // when greater than previous best // then change it if (i - l + 1 >= end - start + 1 ) { end = i; start = l; } } // print the longest sub-segment for ( int i = start; i <= end; i++) System.out.print(a[i]+ " " ); } // Driver code public static void main(String args[]) { int a[] = { 6 , 5 , 1 , 2 , 3 , 2 , 1 , 4 , 5 }; int n = a.length; int k = 3 ; longest(a, n, k); } } // This code is contributed by // Surendra_Gangwar |
Python 3
# Python 3 program to find longest # subarray with k or less distinct elements. # function to print the longest sub-array import collections def longest(a, n, k): freq = collections.defaultdict( int ) start = 0 end = 0 now = 0 l = 0 for i in range (n): # mark the element visited freq[a[i]] + = 1 # if its visited first time, then increase # the counter of distinct elements by 1 if (freq[a[i]] = = 1 ): now + = 1 # When the counter of distinct elements # increases from k, then reduce it to k while (now > k) : # from the left, reduce the number # of time of visit freq[a[l]] - = 1 # if the reduced visited time element # is not present in further segment # then decrease the count of distinct # elements if (freq[a[l]] = = 0 ): now - = 1 # increase the subsegment mark l + = 1 # check length of longest sub-segment # when greater than previous best # then change it if (i - l + 1 > = end - start + 1 ): end = i start = l # print the longest sub-segment for i in range (start, end + 1 ): print (a[i], end = " " ) # Driver Code if __name__ = = "__main__" : a = [ 6 , 5 , 1 , 2 , 3 , 2 , 1 , 4 , 5 ] n = len (a) k = 3 longest(a, n, k) # This code is contributed # by ChitraNayal |
C#
// C# program to find longest subarray with // k or less distinct elements. using System; class GFG { // function to print the longest sub-array static void longest( int []a, int n, int k) { int [] freq = new int [7]; int start = 0, end = 0, now = 0, l = 0; for ( int i = 0; i < n; i++) { // mark the element visited freq[a[i]]++; // if its visited first time, then increase // the counter of distinct elements by 1 if (freq[a[i]] == 1) now++; // When the counter of distinct elements // increases from k, then reduce it to k while (now > k) { // from the left, reduce the number of // time of visit freq[a[l]]--; // if the reduced visited time element // is not present in further segment // then decrease the count of distinct // elements if (freq[a[l]] == 0) now--; // increase the subsegment mark l++; } // check length of longest sub-segment // when greater than previous best // then change it if (i - l + 1 >= end - start + 1) { end = i; start = l; } } // print the longest sub-segment for ( int i = start; i <= end; i++) Console.Write(a[i]+ " " ); } // Driver code public static void Main(String []args) { int []a = { 6, 5, 1, 2, 3, 2, 1, 4, 5 }; int n = a.Length; int k = 3; longest(a, n, k); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find longest subarray with // k or less distinct elements. // function to print the longest sub-array function longest(a, n, k) { var freq = Array(7).fill(0); var start = 0, end = 0, now = 0, l = 0; for ( var i = 0; i < n; i++) { // mark the element visited freq[a[i]]++; // if its visited first time, then increase // the counter of distinct elements by 1 if (freq[a[i]] == 1) now++; // When the counter of distinct elements // increases from k, then reduce it to k while (now > k) { // from the left, reduce the number of // time of visit freq[a[l]]--; // if the reduced visited time element // is not present in further segment // then decrease the count of distinct // elements if (freq[a[l]] == 0) now--; // increase the subsegment mark l++; } // check length of longest sub-segment // when greater than previous best // then change it if (i - l + 1 >= end - start + 1) { end = i; start = l; } } // print the longest sub-segment for ( var i = start; i <= end; i++) document.write(a[i]+ " " ); } // driver program to test the above function var a = [6, 5, 1, 2, 3, 2, 1, 4, 5]; var n = a.length; var k = 3; longest(a, n, k); </script> |
1 2 3 2 1
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for freq array.