# 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.

## 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 then 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 then 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 then 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 then 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 then 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>` |

**Output:**

1 2 3 2 1

**Time Complexity:** O(n)

This article is contributed by **Striver**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.