Distinct Left

Moderate
0/80
Average time to solve is 20m
5 upvotes
Asked in company
Vir Softech

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 3
1 3 2 2 4
4 2
10 4 8 5
Sample Output 1:
2
2
Explanation for Sample 1:
For the first test case we have 4, 3 and 2 as three maximum elements. After deleting these three elements, we are left with array [1, 2]. Hence, we are left with two distinct elements in the array.

For the second test case we have 10 and 8 as two maximum elements. After deleting these three elements, we are left with array [4, 5]. Hence, we are left with two distinct elements in the array.
Sample Input 2:
1
8 5
4 7 4 6 7 1 2 4
Sample Output 2:
3
Hint

Delete K maximum elements one by one and then find distinct elements left.

Approaches (3)
Brute Force Solution

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.

Time Complexity

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

 

When all the elements are different in the array and ‘K’ = ‘N’, i.e. size of the array, we will end up deleting all the elements. For each deletion, we are taking linear time, and there are at most ‘N’ deletions, so the time complexity is O(N^2).

 

Although set operations take logarithmic time and will take at most N * log(N) operations, the upper bound of the solution remains O(N^2).

Space Complexity

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

 

The nested loops will not use any extra space, but in the worst-case scenario, we might end up inserting almost all the elements in the SET.

Code Solution
(100% EXP penalty)
Distinct Left
Full screen
Console