Find k most occurring elements in an integer array
algorithm, arrays, java
Solution
We can say the space complexity of your approach is `O(n)`, since you can never use more than `O(2n) = O(n)` memory.
Skip the heap and just create the HashMap.
After you've created the HashMap, you can iterate through it and put all the elements in an array.
Then you can run a selection algorithm such as quickselect on the array to get `k`-th element, and the first `k` elements from there (the extension to extract the first `k` elements via quickselect is fairly trivial, or you can just iterating through again to get them).
Then you sort the `k` elements, if required.
The running time would be expected `O(n)` or `O(n + k log k)` if sorting is required.
The space complexity would be `O(n)`.
Problem
Given an array A with possible duplicate entries, find the k entries that occur most frequently. My approach: Create a MinHeap of k most occurring elements ordered by the frequency. top element obviously being least occurring of rest of the elements. Create a HashMap to keep track of all element counts and whether or not they are in MinHeap. When reading a new integer: - check if it is in HashMap: Increment the count in HashMap - also if it is check if it is in Heap :then Increment the count there also and heapify. - if not then compare with root element count and remove the root to add this if necessary. Then heapify. In the end return MinHeap as desired output. ``` class Wrapper{ boolean inHeap; int count; } ``` This would take O(n+k) space and O(n log k) time complexity. Is there a better way to do space and/or time complexity wise.