Longest subarray not having more than K distinct elements

Difficulty Level Medium
Frequently asked in Amazon Citadel Delhivery Facebook Microsoft Samsung Yandex
Array Hash Sliding WindowViews 3601

The problem “Longest subarray not having more than K distinct elements” states that suppose you have an array of integers, the problem statement asks to find out the longest sub-array that having not greater than k different elements.

ExampleLongest subarray not having more than K distinct elements

arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5}
k=3
2, 1, 2, 0

Explanation

Longest sub-array (2, 1, 2, 0) with k distinct elements

arr[] = {1, 2, 3, 4}
k=2
3, 4

Explanation

Longest sub-array (3, 4) with k distinct elements

Algorithm

  1. Increase and keep the count of each element
  2. Starting from 0 maintain a count of distinct elements till it becomes greater than k.
  3. If the count becomes greater than k, start decreasing the count of elements (starting point).
  4. Keep removing the count until we get again k distinct elements also increase the starting point of sub-array.
  5. Update the end according to the array element index by checking the longest sub-array length.
  6. Print the array form starting to end-point.

Explanation

We have given an array of integers, we have asked to find out the longest sub-array present in an array which is having not more than k distinct elements. We are going to use a similar method as hashing. We have to keep increasing the count of each element, although we need to find the longest sub-array. So we have to maintain an eye on the starting point of the sub-array and at the ending point of the sub-array. So, we will print that sub-array from start to end with not more than k distinct elements, given to us.

We also have to maintain the count of that thing which makes sure that no number should exceed greater than k. Let us take an example:

Arr[]={4, 3, 5, 2, 1, 2, 0, 4, 5}, k=3

We pick each element of the array and increase the count of an array element and every time we check if its occurrence is for the first time, we will increase the current count, we are going to compare it with k, we aren’t do anything until it becomes greater than k. if once it becomes greater than k, we will decrease the count of element starting from 0, and make increase the value so that next time we can decrease the count of the next element. We should increase the value of left, it will be the starting point of sub-array till we found again k distinct elements.

If we consider 4, 3 and 5 from an array we have i=2, curr=3, if we go for the next element we get the curr as 4 we get the 2 as the starting point of sub-array and we should keep going until we found the more than k distinct elements.

Code

C++ code to find Longest subarray not having more than K distinct elements

#include<iostream>
#include<unordered_map>
using namespace std;

void getLongestSub(int arr[], int n, int k)
{
    unordered_map<int, int> count;

    int start = 0, endp = 0, curr = 0, left = 0;
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
        if (count[arr[i]] == 1)
            curr++;
        while (curr > k)
        {
            count[arr[left]]--;

            if (count[arr[left]] == 0)
                curr--;

            left++;
        }
        if (i - left + 1 >= endp - start + 1)
        {
            endp = i;
            start = left;
        }
    }
    for (int i = start; i <= endp; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getLongestSub(arr, n, k);
    return 0;
}

2 1 2 0

Java code to find Longest subarray not having more than K distinct elements

import java.util.*;

class longestSubArray
{
    public static void getLongestSub(int arr[], int n, int k)
    {
        int[] count = new int[7];
        int start = 0, end = 0, curr = 0, left = 0;
        for (int i = 0; i < n; i++)
        {
            count[arr[i]]++;
            if (count[arr[i]] == 1)
                curr++;

            while (curr > k)
            {
                count[arr[left]]--;

                if (count[arr[left]] == 0)
                    curr--;
                left++;
            }
            if (i - left + 1 >= end - start + 1)
            {
                end = i;
                start = left;
            }
        }
        for (int i = start; i <= end; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String args[])
    {
        int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
        int n = arr.length;
        int k = 3;
        getLongestSub(arr, n, k);
    }
}

2 1 2 0

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Using a hashmap allows us to insert, delete, and search in O(1) time. Thus the time complexity is linear.

Space Complexity

O(n) where “n” is the number of elements in the array. In the worst-case, we may have to store all the elements. Thus the space complexity is also linear.

Translate »