First K Maximum Elements

Posted: 2 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You have been given an array of ‘N’ integers and an integer 'K'. You have to find the indexes of the first 'K' maximum elements in the array.

Note :

'K' must be less than or equal to the number of distinct elements in the given array.

Consider '0’ based indexing of the elements in the given array.

Print all indexes in increasing order.

For Example :

If, 'ARR' = [4, 2, 4, 2, 1], and K = 2. Then output will be 0, 1, 2, 3.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers ‘N’ and 'K' where ‘N’ is the length of the array, and 'K' is the integer which is described above.

The second line of each test case will contain ‘N’ space-separated integers which denote the elements in the given array.
Output Format :
For each test case, print the indexes of the first 'K' maximum elements in the increasing order.

Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.

There is no need to sort the indexes in increasing order it has already been taken care of.
Constraints :
1 <= T <= 50
1 <= N <= 10000
1 <= K <= Distint Element in ARR
0 <= ARR[i] <= 10 ^ 5

Where 'ARR[i]' is the i'th element of the given array.

Time limit: 1 sec
Approach 1

The basic idea is to put all the elements in a set and arrange them in decreasing order, then find the indexes of the first ‘k’ maximum elements in the input array.

 

The steps are as follows:

  1. Create a set (say, “st”) to store all the distinct elements in decreasing order and a variable named “count” to count the maximum elements traced.
  2. Create a vector of type int (say, “ans”) to store the indexes of maximum elements.
  3. Iterate through the “arr” and keep storing each element into “st”.
  4. Iterate through the “st” (say, iterator = ‘i’).
    • Increment the “count” by 1 and check if “count” becomes greater than ‘k’ then stops the further iterations.
    • Iterate through the “arr” and check if the element at any iteration is equal to the element in “st” at ‘i’ then push its index into the “ans”.
  5. Returns the vector “ans”.
Try Problem