We cannot do it in O(n+k). We will need O(n+klogk).
Why not O(n+k)?
In worst case, if we have k=n distinct elements, then by O(n+k) we are implying that n distinct elements can be sorted in O(n) – which is impossible (without some other special condition, such as range or anything, and there isn’t any such in this question). Here we don’t have the range given explicitly, so at the worst it can be 1 to m where m is the largest element and m can be larger than n itself (m can be O($n^{2}$) or O($n^{3}$) or even higher). So we cannot use the range 1 to m because a simple O(nlogn) solution would be way better than O(m).
How in O(n+klogk)?
- Create a Hash map of all the distinct k elements (similar to the count array we use in counting sort)
- Sort these k elements – this needs to be done explicitly because we have k distinct elements and not a range of 1 to k. This wasn’t needed in counting sort because we can take an array of size k and the indices will be in sorted order only (1 to k) but here this won’t hold true so sorting the distinct elements is needed --- O(klogk)
- Rest is same as counting sort – we store the count of each distinct element and then print them in sorted manner --- O(n)
So time complexity will be O(n + klogk)