Smallest Subarray with K Distinct Elements
Given an array 'A' consisting of 'N' integers, find the smallest subarray of 'A' containing exactly 'K' distinct integers.

Note :

If more than one such contiguous subarrays exist, consider the subarray having the smallest leftmost index. For example - if A is [1, 2, 2, 3, 1, 3 ] and k = 2 then the subarrays: [1,2], [2,3], [3,1], [1,3] are the smallest subarrays containing 2 distinct elements. In this case, we will consider the starting and ending index of subarray [1,2] i.e. 0 and 1.

Input Format :

The first line contains two integers 'N' and 'K' denoting the total number of integers and number of distinct integers respectively. The second line contains 'N' space-separated integers describing elements of the array 'A'.

Output Format :

Print two space-separated integers denoting the starting and ending index of the subarray if it exists, otherwise print -1.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function. Assume array starts with 0 index. If more than one solution is possible then print the subarray with smaller left index.

Constraints :

1

Question

Smallest Subarray with K Distinct Elements

Given an array 'A' consisting of 'N' integers, find the smallest subarray of 'A' containing exactly 'K' distinct integers.

Note :

If more than one such contiguous subarrays exist, consider the subarray having the smallest leftmost index.

For example - if A is [1, 2, 2, 3, 1, 3 ] and k = 2 then the subarrays: [1,2], [2,3], [3,1], [1,3] are the smallest subarrays containing 2 distinct elements. In this case, we will consider the starting and ending index of subarray [1,2] i.e. 0 and 1.

Input Format :

The first line contains two integers 'N' and 'K' denoting the total number of integers and number of distinct integers respectively. 

The second line contains 'N' space-separated integers describing elements of the array 'A'.

Output Format :

Print two space-separated integers denoting the starting and ending index of the subarray if it exists, otherwise print -1.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Assume array starts with 0 index.
If more than one solution is possible then print the subarray with smaller left index.

Constraints :

1 <= N, K <= 10^6
-10^5 <= A[i] <= 10^5

Time limit: 1 sec

Accepted Answer

At first sight this can be solved easily by using two loops to iterate over contiguous subarrays in O(n^2) and counting number of arrays and breaking the outer loop if number of odds exceed 'k'.

Optimised solution is to take two pointer approach where right pointer is incremented till num of odds not exceed 'k'. If limit is reached, increment left pointer and add number of arrays (right - left+1)*(right-left)/2 to the result. This solves the problem in O(N)

Accepted Answer

Brute Force Approach

Algorithm

Pick each element from the array as the starting element(i) of the subarray,
- Initialize an empty set to store distinct elements in the subarray.
- Pick each remaining element(i, i+1,..n - 1) from the array as the last element(jth).
  - Add the current element to the set.
  - If the set size equals k then update the results and break from the inner loop(we have already found k distinct elements increasing the size of the subarray will either make more distinct elements or increase the subarray size with repeated elements which are not to be considered in the required results).
- If j == size of the array, it means we have not found any desired subarray starting from ith index and going forward we will be having fewer elements to consider. Break from the outer loop
Print the output if found, otherwise, print “-1”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

In the worst case, we can have all ‘N’ elements in our set.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of elements in the array.

Picking the ends of the subarray using two nested loops(one inside another) makes the time complexity O(N^2).

Accepted Answer

Sliding Window Approach

Using the sliding window technique

Algorithm

Initialize the map to store the count of each element.
Initialize start and end to store the index of the required subarray.
i, j denote the start and end of the window, i = 0, j = 0
While the end < size of the array,
- In the map, increase the count of the end index's character by 1, if the character is not present in the map, increment the value of count.
- While the count of distinct elements equals K (i.e. the size of the map is equal to K)
  - Find the length of subarray as j - i
  - Compare it with the length of the minimum length you've found so far (initially 0)
  - If the current length is less than the minimum, update the minimum length
  - From the left side, i.e. i's side, decrease the count of ith character by 1. If it is already one, remove that character from the map
  - Move i forward by 1
If end is equal to n, that means no subarray was found with K distinct characters and we can print -1. Otherwise, we can print the start and end index we found.

Space Complexity: OtherExplanation:

O(K), where ‘K' is given integer.

In the worst case, we will be only having K elements in our map.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

In the worst case, each element will be added once and removed once from the set.

Accepted Answer

simple make a window and keep on moving starting with i=0, j=0, keep increasing j until it is visited so yes a visited map is requried., and manage MaxAchieved till Now;

Given an array 'A' consisting of 'N' integers, find the smallest subarray of 'A' containing exactly 'K' distinct integers.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Uber SDE-2 interview questions & answers

Popular interview questions of SDE-2