Last Updated: 22 Sep, 2020
Distinct Left
Moderate
Asked in company
You have been given an array/list of integers 'ARR' of size 'N'. You are also provided an integer 'K'.
Your task is to find the number of distinct elements left in the array, after deleting 'K' maximum elements from the array.
For example:
For the given array arr = [5, 3, 2, 3, 4, 3] and K = 3.
Output = 2
We have to delete three maximum elements, i.e. 5, 4, and 3. So, the array after the deletions contains 2, 3, and 3. Now, we only have two distinct elements left in the array (2 and 3).
Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case contains two single space-separated integers 'N' and 'K' representing the size of the array/list and the given integer respectively.
The second line of each test case contains 'N' single space-separated integers representing the array/list elements.
Output Format:
For each test case, print a single integer, i.e. the number of distinct elements left in the array/list.
Print output of each test case in a separate line.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
1 <= K <= N
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
The naive solution is to delete those K maximum elements one by one. We will use two nested loops for this. The outer loop runs ‘K’ times while the inner loop traverses the whole array and finds the maximum element. So, each time we will be deleting a maximum element from the array (maximum ‘K’ times).
Now, we can use a SET data structure to count the distinct elements left in the array. We just insert all the remaining elements into our SET, and then the size of the SET will be our count of distinct elements left in the array.
The better idea is to sort the given array in decreasing order. Now, we know that we can count the number of distinct elements in an array with the help of a SET data structure. So we skip the first ‘K’ elements in the array as they are eventually going to be deleted and insert the rest of the array elements into our SET. The final size of the SET will be our count of distinct elements left in the array.
After sorting the array in descending order and skipping the first ‘K’ elements, we can count the number of distinct elements in the rest of the array in linear time and constant space.
We will traverse in the rest of the array, and whenever an element is found different from its adjacent previous element (i.e. ARR[i] != ARR[i-1]), we know we found a new element. So, we increase the ‘DISTINCT_COUNT’ by 1.
Similar problems