How to Find the k‑th Largest Element in an Unsorted Array: 4 Efficient Methods

Problem Statement

Given an unsorted array, the task is to find the k‑th largest element.

Example array (k=6) where the 6th largest element is 9:

Method 1: Sorting

Sort the array in descending order and directly pick the element at position k. This straightforward approach has a time complexity of O(n log n).

Method 2: Insertion

Maintain a sorted auxiliary array A of length k that stores the current k largest elements while scanning the original array. For each new element, compare it with the smallest element in A; if it is larger, insert it into the proper position and eject the smallest element.

Method 3: Min‑Heap

Maintain a min‑heap of size k. The heap always contains the k largest elements seen so far, and its root is the smallest among them, i.e., the current k‑th largest element. After processing the whole array, the heap root is the desired answer.

Complexities:

Build heap: O(k)

Process remaining elements: O((n‑k) log k)

Overall worst‑case time: O((n‑k) log k + k) ≈ O(n log k) when k ≪ n

Space: O(1) if the heap is built in‑place

Java Implementation

public class KthLargestNumber {
    /**
     * Find the k‑th largest element
     * @param array the input array (used as heap)
     * @param k the order statistic
     */
    public static int findKthLargestNumber(int[] array, int k) {
        // 1. Build a min‑heap with the first k elements
        buildHeap(array, k);
        // 2. Scan the rest of the array
        for (int i = k; i < array.length; i++) {
            if (array[i] > array[0]) {
                array[0] = array[i];
                downAdjust(array, 0, k);
            }
        }
        // 3. Heap root is the k‑th largest
        return array[0];
    }

    /** Build a heap */
    private static void buildHeap(int[] array, int length) {
        for (int i = (length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, length);
        }
    }

    /** Down‑adjust (heapify) */
    private static void downAdjust(int[] array, int index, int length) {
        int temp = array[index];
        int childIndex = 2 * index + 1;
        while (childIndex < length) {
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            if (temp <= array[childIndex]) {
                break;
            }
            array[index] = array[childIndex];
            index = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[index] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{7,5,15,3,17,2,20,24,1,9,12,8};
        System.out.println(findKthLargestNumber(array, 5));
    }
}

Method 4: Divide and Conquer (Quickselect)

Apply the quicksort partitioning idea repeatedly: choose a pivot, move elements larger than the pivot to the left side and smaller ones to the right. If the number of elements on the left equals k, the pivot is the answer; otherwise continue in the appropriate sub‑array.

This approach achieves expected linear time O(n) and is often the fastest in practice.

Further Reading

For more detailed explanations and additional examples, see the book 漫画算法2：小灰的算法进阶 by 魏梦舒.