Solution
Intuition
If k = 1
the lineartime solution is quite simple. One could keep
the frequency of elements appearance in a hash map and update the maximum
element at each step.
When k > 1
we need a data structure that
has a fast access to the elements
ordered by their frequencies.
The idea here is to use the heap which is also known as priority queue.
Approach 1: Heap
The first step is to build a hash map element > its frequency
.
In Java we could use data structure HashMap
but have to fill it manually.
Python provides us both a dictionary structure for the hash map and
a method Counter
in the collections
library
to build the hash map we need.
This step takes time where N
is number of elements
in the list.
The second step is to build a heap.
The time complexity of adding an element in a heap
is and we do it N
times that means
time complexity for this step.
The last step to build an output list has
time complexity.
In Python there is a method nlargest
in heapq
library
(check here the source code)
which has the same time complexity
and combines two last steps in one line.
!?!../Documents/347_LIS.json:1000,498!?!
Complexity Analysis

Time complexity : . The complexity of
Counter
method is . To build a heap and output list takes . Hence the overall complexity of the algorithm is . 
Space complexity : to store the hash map.
Side Notes
Following the complexity analysis, the approach is
optimal for small k
. In the case of large k
, one could
revert the procedure by excluding the less frequent elements from
the output.