mediumHeap / Priority Queue

Kth Largest Element in an Array

Find the kth largest array value, counting duplicate values separately.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated integers on line 1. Valid k on line 2, counting from 1.

Expected result

The kth largest value.

Case 1

Input

4 1 7 7 3
2

Expected output

Case 2

Input

-5 -2
1

Expected output

-2

Case 3

Input

5 5 5
3

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Full sorting finds the k-th largest but orders every other position as well. Quickselect only needs the side that contains that rank. After partitioning around a pivot we recurse only into the interval that holds the target. The implementation converts “ k-th largest” into “ (n-k)-th smallest”.

Quick Select is an algorithm for finding the k^{th} largest or smallest element in an unsorted array. Its basic idea is to select a pivot element each time, dividing the array into two parts: one part contains elements smaller than the pivot, and the other part contains elements larger than the pivot. Then, based on the position of the pivot, it decides whether to continue the search on the left or right side until the k^{th} largest element is found.

The time complexity is O(n), and the space complexity is O(log n). Here, n is the length of the array nums.

class Solution {
    private int[] nums;
    private int k;

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        this.k = nums.length - k;
        return quickSort(0, nums.length - 1);
    }

    private int quickSort(int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int i = l - 1, j = r + 1;
        int x = nums[(l + r) >>> 1];
        while (i < j) {
            while (nums[++i] < x) {
            }
            while (nums[--j] > x) {
            }
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        if (j < k) {
            return quickSort(j + 1, r);
        }
        return quickSort(l, j);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.