# Java O(n) solution with O(n) extra memory: k-th order statistics

• The idea is to use algorithm for finding kth-order statistics in array.

1. Create frequency map: go through array and count each element in Map<Integer, Integer> - O(n)
2. Create array of pairs from that map, such that each pair is (v,f) - where v -actual value, f - number of times that this value appears in array. O(n)
3. Using 'quicksort' like algorithm find k-th element in array of pairs (where key is frequency) (details about algorithm) - O(n)
4. Now all elements before that k-th element will be most frequent values in a array
``````class Solution {

/*
* Aux class to store tuble (v, f) - where
* v - actual value, f - number of times that value 'v'
* appears in array
*/
class Pair{

final int freq;
final int val;

Pair(int val, int freq){
this.val = val;
this.freq = freq;
}
}

static Random rnd = new Random();

public List<Integer> topKFrequent(int[] nums, int k) {
if(nums.length == 1) return Arrays.asList(nums[0]);
Map<Integer, Integer> freqMap = createFreqMap(nums);
// array of frequencies from freqMap
Pair[] pairs = new Pair[freqMap.size()];
int j = 0;
for(Integer kk: freqMap.keySet()){
pairs[j++] = new Pair(kk, freqMap.get(kk));
}
if(pairs.length == 1) return Arrays.asList(pairs[0].val);
// here we are trying to find k-th ordeer statistics
int low = 0;
int high = pairs.length;
while (true) {
if(high <= low) break;
int n = randomizedPartition(pairs, low, high);
if (k < n)
high = n;
else if (k > n)
low = n + 1;
else
break;
}
for(int jj=0;jj<k;jj++){
}
return result;
}

/*
* Frequency map, where key is actual value from int[] nums
* and value is number of times that value appears in int[] nums.
* Complexity - O(n)
*/
static Map<Integer, Integer> createFreqMap(int[] nums) {
Hash<Integer, Integer> freqMap = new HashMap<>();
for(Integer n: nums){
frqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
}
return freqMap;
}

static int randomizedPartition(Pair[] a, int low, int high) {
swap(a, low + rnd.nextInt(high - low), high - 1);
Pair separator = a[high - 1];
int i = low - 1;
for (int j = low; j < high; j++)
if (a[j].freq >= separator.freq)
swap(a, ++i, j);
return i;
}

static void swap(Pair[] a, int i, int j) {
Pair t = a[i];
a[i] = a[j];
a[j] = t;
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.