# 347. Top K Frequent Elements

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mh3Hnf7TovrT_oZq545%2F-Mh3MPobaF33SW4FNtxB%2Fimage.png?alt=media\&token=a3a12597-ff51-45d3-8c30-7e94fdfab08f)

## Quick select

use quick select is too complex, this Q can be solved by **bucket sort.**

time: O(n)

space: O(m), map size

**idea** - use map to count, then gen a new array to do the quick select

just the compare condition becomes like this:

```java
if (count.get(nums[i]) < count.get(nums[pivot]))
```

```java
class Solution {
    Map<Integer, Integer> count;
    
    public int[] topKFrequent(int[] nums, int k) {
        count = new HashMap();
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // array of unique elements
        int n = count.size();
        int[] unique = new int[n]; 
        int i = 0;
        for (int num: count.keySet()) {
            unique[i] = num;
            i++;
        }
        
        findKthSmallest(unique, 0, n - 1, n - k);
        
        return Arrays.copyOfRange(unique, n - k, n);
        
    }
    
    private void findKthSmallest(int nums[], int left, int right, int ksmallest) {
        if (left == right) return; // only one element

        int pivot = partition(nums, left, right);
        
        if (ksmallest == pivot) { // bingo!
            return;
        } else if (ksmallest < pivot) { // find left side
            findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int nums[], int left, int right) {
        int pivot = right;
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (count.get(nums[i]) < count.get(nums[pivot])) { // here is different
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, pivot);
        return storedIndex;
    }
    
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```

## Random Pivot

```java
class Solution {
    Map<Integer, Integer> count;
    
    public int[] topKFrequent(int[] nums, int k) {
        count = new HashMap();
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // array of unique elements
        int n = count.size();
        int[] unique = new int[n]; 
        int i = 0;
        for (int num: count.keySet()) {
            unique[i] = num;
            i++;
        }
        
        findKthSmallest(unique, 0, n - 1, n - k);
        
        return Arrays.copyOfRange(unique, n - k, n);
        
    }
    
    private void findKthSmallest(int nums[], int left, int right, int ksmallest) {
        if (left == right) return; // only one element

        Random random = new Random();
        int randomPivot = left + random.nextInt(right - left);
        int pivot = partition(nums, left, right, randomPivot);
        
        if (ksmallest == pivot) { // bingo!
            return;
        } else if (ksmallest < pivot) { // find left side
            findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int nums[], int left, int right, int pivot) {
        int pivotVal = count.get(nums[pivot]);
        swap(nums, pivot, right);
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (count.get(nums[i]) < pivotVal) { // here is different
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, right);
        return storedIndex;
    }
    
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/kth/347.-top-k-frequent-elements.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.