9.9 Top K Elements

9.9.1 Problem Metadata

9.9.2 Description

Given an unsorted array nums and an integer k, return the k largest elements. The order of the result can be either sorted descending or unspecified depending on the approach.

9.9.3 Examples

Input: nums = [3,2,1,5,6,4], k = 2
Output: [6,5]

9.9.4 Constraints

  • 1 <= k <= n <= 10^5
  • -10^4 <= nums[i] <= 10^4

9.9.5 Solution 1 - Sort Then Slice

9.9.5.1 Walkthrough

Sort the entire array in ascending order and copy the last k values, reversing if descending order is required. This is simple but costs O(n log n).

9.9.5.2 Analysis

  • Time Complexity: O(n log n)
  • Space Complexity: O(1) auxiliary (in-place sort)

9.9.5.3 Implementation Steps

  1. Sort nums ascending.
  2. Copy elements from n - k to n - 1 into the answer array (optionally reverse).

9.9.5.4 Code - Java

public int[] topKBySorting(int[] nums, int k) {
    Arrays.sort(nums);
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = nums[nums.length - 1 - i];
    }
    return result;
}

9.9.6 Solution 2 - Partial Bubble (k Passes)

9.9.6.1 Walkthrough

Bubble sort guarantees that after one full pass the largest element bubbles to the end. Running only k passes yields the k largest elements at the array tail without fully sorting the remainder.

9.9.6.2 Analysis

  • Time Complexity: O(n * k)
  • Space Complexity: O(1)

9.9.6.3 Implementation Steps

  1. Repeat k times:
    1. Sweep the array bubbling the largest remaining element to the end.
  2. Read off the last k positions as the answer.

9.9.6.4 Code - Java

public int[] topKByPartialBubble(int[] nums, int k) {
    for (int pass = 0; pass < k; pass++) {
        for (int j = 0; j < nums.length - pass - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = nums[nums.length - 1 - i];
    }
    return result;
}

9.9.7 Solution 3 - Min Heap of Size k

9.9.7.1 Walkthrough

Maintain a min heap that stores the current k largest numbers. Push each number and pop whenever the heap size exceeds k. After processing all numbers the heap contains exactly the answer set, and polling yields increasing order.

9.9.7.2 Analysis

  • Time Complexity: O(n log k)
  • Space Complexity: O(k)

9.9.7.3 Implementation Steps

  1. Initialize an empty min heap.
  2. For each num in nums, push it; if heap size exceeds k, pop the smallest.
  3. Extract remaining heap elements into the answer array (reverse if descending needed).

9.9.7.4 Code - Java

public int[] topKByMinHeap(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = heap.poll();
    }
    return result;
}