Skip to content

215. Kth Largest Element in an Array

Question

Given an unsorted integer array nums and an integer k, return the \(k^{th}\) largest element in the array.

Note: It is the \(k^{th}\) largest element in sorted order, not the \(k^{th}\) distinct element.

Solution

Pattern

Quickselect (Hoare's / Lomuto Partitioning) A selection algorithm related to Quicksort. Instead of sorting both sides of a partition, we only recurse into the side containing our target index.

How to Identify

  • Find the \(k^{th}\) smallest/largest element.
  • Requirement for \(O(n)\) average time complexity.
  • Constraints suggest that sorting (\(O(n \log n)\)) is too slow or unnecessary.

Description

Step-by-step explanation:

  1. Target Index: In a sorted array of size \(n\), the \(k^{th}\) largest element is at index target = n - k.
  2. Partitioning: Pick a pivot (randomly to avoid worst-case). Move all elements smaller than the pivot to its left and larger to its right.
  3. Check Pivot Position: After partitioning, the pivot is in its final sorted position i.
    • If i == target, you found the element.
    • If i > target, search the left partition.
    • If i < target, search the right partition.
  4. Repeat: Continue until the search range narrows to the target index.

The Intuition

Think of Quickselect as "Goal-Oriented Quicksort". In Quicksort, you are trying to organize the entire room. In Quickselect, you only care about who sits in the \(k^{th}\) chair. Once you partition the room, if the \(k^{th}\) chair is on the left side, you completely ignore everyone on the right.

Why \(O(n)\) and not \(O(\log n)\)?

  • Level 1: Scan \(n\) elements.
  • Level 2: Scan \(n/2\) elements.
  • Level 3: Scan \(n/4\) elements.
  • Sum: \(n(1 + 1/2 + 1/4 + \dots) \approx 2n\), which is \(O(n)\).

Complexity

Label Worst Average
Time Complexity \(O(n^2)\) \(O(n)\)
Space Complexity \(O(1)\) \(O(1)\)

Time Complexity

Average case is linear because the problem size reduces geometrically. Worst case (highly skewed partitions) is \(O(n^2)\), though randomized pivoting makes this nearly impossible in practice.

Space Complexity

Strictly \(O(1)\) if implemented iteratively. Recursive implementations use \(O(\log n)\) stack space on average.

Code

import java.util.Random;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int target = n - k; // Index in sorted array
        int start = 0, end = n - 1;
        Random rand = new Random();

        while (start <= end) {
            // Randomized pivot to prevent O(n^2)
            int pivotIndex = start + rand.nextInt(end - start + 1);
            int pivotPos = partition(nums, start, end, pivotIndex);

            if (pivotPos == target) {
                return nums[pivotPos];
            } else if (pivotPos < target) {
                start = pivotPos + 1;
            } else {
                end = pivotPos - 1;
            }
        }
        return -1;
    }

    private int partition(int[] nums, int start, int end, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, end); // Move pivot to end
        int storeIndex = start;

        for (int i = start; i < end; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, i, storeIndex);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, end); // Move pivot to its final place
        return storeIndex;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Caveats

  • Modifies Input: Quickselect is an in-place algorithm. If you cannot modify the original array, you must use a Min-Heap (\(O(n \log k)\) time, \(O(k)\) space).
  • Duplicate Elements: Standard partitioning handles duplicates, but very large numbers of identical elements can lead to skewed partitions.
  • Worst Case: Always mention that while average is \(O(n)\), the theoretical worst case is \(O(n^2)\).

Concepts to Think About

  • Min-Heap Approach: Useful if \(k\) is very small compared to \(n\) or if data is streaming.
  • Hoare vs. Lomuto: Hoare's partition uses two pointers from both ends and is generally faster with fewer swaps.
  • Median of Medians: The "Introselect" algorithm uses this to ensure \(O(n)\) worst-case.
  • Introselect: Used in C++ std::nth_element, which switches from Quickselect to Heapsort if recursion goes too deep.

Logical Follow-up

Question: What if the array is too large to fit in memory? Solution: Use a Min-Heap of size \(k\). Iterate through the file, keeping only the \(k\) largest elements seen so far in the heap. Space: \(O(k)\), Time: \(O(n \log k)\).

Question: What if the numbers are in a specific range (e.g., 1 to 1000)? Solution: Use Counting Sort logic. Count frequencies and iterate from 1000 downwards until you hit the \(k^{th}\) element. Time: \(O(n + Range)\).

Solution 2 (using heap)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for ( int i = 0; i < nums.length; ++i) {
        minHeap.add(nums[i]);

        // to ensure we keep the K smallest element
        if (minHeap.size() > k) {
            minHeap.remove();
        }
    }

    return minHeap.peek();        
}

Comments