First K Maximum Elements

Easy
0/40
Average time to solve is 10m
4 upvotes
Asked in companies
AmazonProdapt SolutionsD.E.Shaw

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 2
4 2 4 2 1
1 1
5
Sample Output 1 :
0 1 2 3
0
Explanation of sample input 1 :
In the first test case, the first 2 maximum elements are 4, and 2.

In the second test case, there is a single element that itself a maximum.
Sample Input 2 :
2
4 3
1 2 3 4
6 1
2 2 2 2 2 2
Sample Output 2 :
1 2 3
0 1 2 3 4 5
Explanation of sample input 2 :
In the first test case, the first 3 maximum elements are 4, 3, and 2.

In the second test case, all elements are the same and so, maximum exists at every index.
Hint

Can you find the solution by calculating the indexes of maximum element one by one?

Approaches (2)
Brute Force

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”.
Time Complexity

O(N*K), where ‘N’ is the length of the given array and ‘K’ is the required number of maximum elements.

 

First, we are adding each element into the set which costs O(N*log(N)) time because insertion in an ordered set takes O(logN) time and we are also Iterating through the input array.

 

Second, we are iterating through the set till we will find the first ‘k’ maximum elements and inside this loop, we are also iterating through the input array which takes O(N*K) time in total. So, the total time complexity will be O(N*log(N)) + O(N*K). Hence, the overall time complexity will be O(N*K).

Space Complexity

O(N), where ‘N’ is the length of the given array.

 

Since we are using an additional vector to store the answer and a set to store the elements, so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
First K Maximum Elements
Full screen
Console