Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Language Selection

Choose your preferred programming language

Showing: Python

Kth Largest Element in an Array

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Examples

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: The sorted array is [1,2,3,4,5,6]. The 2nd largest element is 5.

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: The sorted array is [1,2,2,3,3,4,5,5,6]. The 4th largest element is 4.

Example 3:

Input: nums = [1], k = 1
Output: 1
Explanation: The only element is the 1st largest.

Constraints

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

Approach 1: Sorting

Algorithm Explanation

The simplest approach is to sort the array and return the element at index n - k (or equivalently sort in descending order and return the element at index k - 1).

Steps:

  1. Sort the array in ascending order.
  2. Return nums[n - k].

Implementation

Python:

def findKthLargest(nums, k):
    """
    Find kth largest element by sorting.
    Time: O(n log n)
    Space: O(1) if in-place sort, O(n) otherwise
    """
    nums.sort()
    return nums[len(nums) - k]

Java:

import java.util.Arrays;

class Solution {
    /**
     * Find kth largest element by sorting.
     * Time: O(n log n)
     * Space: O(log n) for sort stack
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Go:

import "sort"

// findKthLargestSort finds kth largest element by sorting.
// Time: O(n log n), Space: O(1)
func findKthLargestSort(nums []int, k int) int {
    sort.Ints(nums)
    return nums[len(nums)-k]
}

JavaScript:

/**
 * Find kth largest element by sorting.
 * Time: O(n log n)
 * Space: O(log n) for sort stack
 */
function findKthLargestSort(nums, k) {
    nums.sort((a, b) => a - b);
    return nums[nums.length - k];
}

C#:

using System;

public class Solution {
    /// <summary>
    /// Find kth largest element by sorting.
    /// Time: O(n log n)
    /// Space: O(log n) for sort stack
    /// </summary>
    public int FindKthLargestSort(int[] nums, int k) {
        Array.Sort(nums);
        return nums[nums.Length - k];
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) – dominated by the sort.
  • Space Complexity: O(1) for in-place sorts (Python’s Timsort uses O(n) auxiliary space in the worst case; Java’s dual-pivot quicksort uses O(log n) stack).

Approach 2: Min-Heap of Size K

Algorithm Explanation

Maintain a min-heap of size k. After processing all elements, the heap contains the k largest elements, and the root (minimum of those k elements) is exactly the kth largest.

Steps:

  1. Iterate through the array.
  2. Push each element onto the heap.
  3. If the heap size exceeds k, pop the smallest element.
  4. After processing all elements, the heap root is the kth largest.

Implementation

Python:

import heapq

def findKthLargestHeap(nums, k):
    """
    Find kth largest element using a min-heap of size k.
    Time: O(n log k)
    Space: O(k)
    """
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return min_heap[0]

Java:

import java.util.PriorityQueue;

class Solution {
    /**
     * Find kth largest element using a min-heap of size k.
     * Time: O(n log k)
     * Space: O(k)
     */
    public int findKthLargestHeap(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

Go:

import "container/heap"

// IntMinHeap implements heap.Interface for a min-heap of ints.
type IntMinHeap []int

func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntMinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntMinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    val := old[n-1]
    *h = old[:n-1]
    return val
}

// findKthLargestHeap finds kth largest element using a min-heap of size k.
// Time: O(n log k), Space: O(k)
func findKthLargestHeap(nums []int, k int) int {
    h := &IntMinHeap{}
    heap.Init(h)

    for _, num := range nums {
        heap.Push(h, num)
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    return (*h)[0]
}

JavaScript:

/**
 * MinHeap implementation for finding kth largest.
 */
class MinHeap {
    constructor() { this.data = []; }

    size() { return this.data.length; }
    peek() { return this.data[0]; }

    push(val) {
        this.data.push(val);
        this._bubbleUp(this.data.length - 1);
    }

    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            this._sinkDown(0);
        }
        return top;
    }

    _bubbleUp(i) {
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (this.data[parent] <= this.data[i]) break;
            [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
            i = parent;
        }
    }

    _sinkDown(i) {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] < this.data[smallest]) smallest = l;
            if (r < n && this.data[r] < this.data[smallest]) smallest = r;
            if (smallest === i) break;
            [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
            i = smallest;
        }
    }
}

/**
 * Find kth largest element using a min-heap of size k.
 * Time: O(n log k)
 * Space: O(k)
 */
function findKthLargestHeap(nums, k) {
    const heap = new MinHeap();

    for (const num of nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop();
        }
    }

    return heap.peek();
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find kth largest element using a min-heap of size k.
    /// Time: O(n log k)
    /// Space: O(k)
    /// </summary>
    public int FindKthLargestHeap(int[] nums, int k) {
        var minHeap = new PriorityQueue<int, int>();

        foreach (int num in nums) {
            minHeap.Enqueue(num, num);
            if (minHeap.Count > k) {
                minHeap.Dequeue();
            }
        }

        return minHeap.Peek();
    }
}

Complexity Analysis

  • Time Complexity: O(n log k) – each of the n elements requires at most an O(log k) heap operation.
  • Space Complexity: O(k) – the heap stores at most k elements.

Approach 3: Quickselect (Optimal)

Algorithm Explanation

Quickselect is a selection algorithm based on the partitioning step of quicksort. It runs in O(n) average time by only recursing into the partition that contains the desired element.

Steps:

  1. Choose a random pivot.
  2. Partition the array so that elements greater than the pivot are on the left and elements less than the pivot are on the right.
  3. If the pivot lands at index k - 1, return it.
  4. If k - 1 is to the left of the pivot, recurse into the left partition.
  5. Otherwise, recurse into the right partition.

Using a random pivot avoids the O(n^2) worst case in practice.

Implementation

Python:

import random

def findKthLargestQuickselect(nums, k):
    """
    Find kth largest element using Quickselect.
    Time: O(n) average, O(n^2) worst case
    Space: O(1)
    """
    def partition(left, right, pivot_idx):
        pivot_val = nums[pivot_idx]
        # Move pivot to end
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        store = left
        for i in range(left, right):
            if nums[i] > pivot_val:  # descending for kth largest
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[right] = nums[right], nums[store]
        return store

    left, right = 0, len(nums) - 1
    target_idx = k - 1

    while left <= right:
        pivot_idx = random.randint(left, right)
        pivot_pos = partition(left, right, pivot_idx)

        if pivot_pos == target_idx:
            return nums[pivot_pos]
        elif pivot_pos < target_idx:
            left = pivot_pos + 1
        else:
            right = pivot_pos - 1

    return -1  # Should not reach here

Java:

import java.util.Random;

class Solution {
    private Random rand = new Random();

    /**
     * Find kth largest element using Quickselect.
     * Time: O(n) average, O(n^2) worst case
     * Space: O(1)
     */
    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int targetIdx = k - 1;

        while (left <= right) {
            int pivotIdx = left + rand.nextInt(right - left + 1);
            int pivotPos = partition(nums, left, right, pivotIdx);

            if (pivotPos == targetIdx) {
                return nums[pivotPos];
            } else if (pivotPos < targetIdx) {
                left = pivotPos + 1;
            } else {
                right = pivotPos - 1;
            }
        }

        return -1;
    }

    private int partition(int[] nums, int left, int right, int pivotIdx) {
        int pivotVal = nums[pivotIdx];
        swap(nums, pivotIdx, right);
        int store = left;

        for (int i = left; i < right; i++) {
            if (nums[i] > pivotVal) { // descending for kth largest
                swap(nums, store, i);
                store++;
            }
        }

        swap(nums, store, right);
        return store;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Go:

import "math/rand"

// findKthLargestQuickselect finds kth largest element using Quickselect.
// Time: O(n) average, O(n^2) worst case
// Space: O(1)
func findKthLargestQuickselect(nums []int, k int) int {
    left, right := 0, len(nums)-1
    targetIdx := k - 1

    for left <= right {
        pivotIdx := left + rand.Intn(right-left+1)
        pivotPos := partition(nums, left, right, pivotIdx)

        if pivotPos == targetIdx {
            return nums[pivotPos]
        } else if pivotPos < targetIdx {
            left = pivotPos + 1
        } else {
            right = pivotPos - 1
        }
    }

    return -1
}

func partition(nums []int, left, right, pivotIdx int) int {
    pivotVal := nums[pivotIdx]
    nums[pivotIdx], nums[right] = nums[right], nums[pivotIdx]
    store := left

    for i := left; i < right; i++ {
        if nums[i] > pivotVal { // descending for kth largest
            nums[store], nums[i] = nums[i], nums[store]
            store++
        }
    }

    nums[store], nums[right] = nums[right], nums[store]
    return store
}

JavaScript:

/**
 * Find kth largest element using Quickselect.
 * Time: O(n) average, O(n^2) worst case
 * Space: O(1)
 */
function findKthLargestQuickselect(nums, k) {
    let left = 0, right = nums.length - 1;
    const targetIdx = k - 1;

    function partition(lo, hi, pivotIdx) {
        const pivotVal = nums[pivotIdx];
        [nums[pivotIdx], nums[hi]] = [nums[hi], nums[pivotIdx]];
        let store = lo;

        for (let i = lo; i < hi; i++) {
            if (nums[i] > pivotVal) { // descending for kth largest
                [nums[store], nums[i]] = [nums[i], nums[store]];
                store++;
            }
        }

        [nums[store], nums[hi]] = [nums[hi], nums[store]];
        return store;
    }

    while (left <= right) {
        const pivotIdx = left + Math.floor(Math.random() * (right - left + 1));
        const pivotPos = partition(left, right, pivotIdx);

        if (pivotPos === targetIdx) {
            return nums[pivotPos];
        } else if (pivotPos < targetIdx) {
            left = pivotPos + 1;
        } else {
            right = pivotPos - 1;
        }
    }

    return -1;
}

C#:

using System;

public class Solution {
    private Random rand = new Random();

    /// <summary>
    /// Find kth largest element using Quickselect.
    /// Time: O(n) average, O(n^2) worst case
    /// Space: O(1)
    /// </summary>
    public int FindKthLargest(int[] nums, int k) {
        int left = 0, right = nums.Length - 1;
        int targetIdx = k - 1;

        while (left <= right) {
            int pivotIdx = left + rand.Next(right - left + 1);
            int pivotPos = Partition(nums, left, right, pivotIdx);

            if (pivotPos == targetIdx) {
                return nums[pivotPos];
            } else if (pivotPos < targetIdx) {
                left = pivotPos + 1;
            } else {
                right = pivotPos - 1;
            }
        }

        return -1;
    }

    private int Partition(int[] nums, int left, int right, int pivotIdx) {
        int pivotVal = nums[pivotIdx];
        (nums[pivotIdx], nums[right]) = (nums[right], nums[pivotIdx]);
        int store = left;

        for (int i = left; i < right; i++) {
            if (nums[i] > pivotVal) { // descending for kth largest
                (nums[store], nums[i]) = (nums[i], nums[store]);
                store++;
            }
        }

        (nums[store], nums[right]) = (nums[right], nums[store]);
        return store;
    }
}

Complexity Analysis

  • Time Complexity: O(n) average. Each partitioning step processes the current range, and on average the range halves each time, giving T(n) = n + n/2 + n/4 + … = O(n). Worst case is O(n^2) but randomized pivoting makes this extremely unlikely.
  • Space Complexity: O(1) – the iterative version uses no extra space beyond a few variables.

Key Insights

  1. Quickselect vs Sorting: Sorting gives O(n log n). Quickselect achieves O(n) average by only processing the partition that contains the target index, discarding the other half.
  2. Min-Heap of Size K: A min-heap of size k naturally maintains the k largest elements. The root is the kth largest. This is O(n log k), which is better than sorting when k is small.
  3. Random Pivot: Choosing a random pivot for quickselect avoids adversarial worst-case inputs (sorted or reverse-sorted arrays) that would cause O(n^2) behavior with a fixed pivot.
  4. Kth Largest as (n-k)th Smallest: The kth largest element in a 0-indexed sorted (ascending) array sits at index n - k. Quickselect can target either index.
  5. Trade-off Decision: Use the heap approach when you cannot modify the input array or when k is much smaller than n. Use quickselect when in-place modification is acceptable and you want O(n) average time.

Edge Cases

  1. k = 1: Return the maximum element.
  2. k = n: Return the minimum element.
  3. Single Element: nums = [7], k = 1 – only one element.
  4. All Duplicates: nums = [5,5,5,5], k = 2 – kth largest is still 5.
  5. Negative Numbers: nums = [-3,-1,-2], k = 1 – maximum is -1.
  6. k = n/2: Median-finding case.

Test Cases

def test_findKthLargest():
    # Test case 1: Basic
    assert findKthLargest([3, 2, 1, 5, 6, 4], 2) == 5

    # Test case 2: Duplicates
    assert findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4

    # Test case 3: Single element
    assert findKthLargest([1], 1) == 1

    # Test case 4: k equals array length (minimum)
    assert findKthLargest([3, 2, 1, 5, 6, 4], 6) == 1

    # Test case 5: k = 1 (maximum)
    assert findKthLargest([3, 2, 1, 5, 6, 4], 1) == 6

    # Test case 6: All same values
    assert findKthLargest([5, 5, 5, 5], 2) == 5

    # Test case 7: Negative numbers
    assert findKthLargest([-1, -3, 2, 0, 1], 2) == 1

    # Test case 8: Two elements
    assert findKthLargest([1, 2], 1) == 2
    assert findKthLargest([1, 2], 2) == 1

    # Test heap approach
    assert findKthLargestHeap([3, 2, 1, 5, 6, 4], 2) == 5
    assert findKthLargestHeap([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4

    # Test quickselect approach
    assert findKthLargestQuickselect([3, 2, 1, 5, 6, 4], 2) == 5
    assert findKthLargestQuickselect([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4

    print("All tests passed!")

test_findKthLargest()

Common Mistakes

  1. Off-by-One Index: Confusing 0-indexed and 1-indexed when converting “kth largest” to an array index. The kth largest is at index n - k in a sorted ascending array, or index k - 1 in a sorted descending array.
  2. Wrong Heap Type: Using a max-heap instead of a min-heap. A min-heap of size k keeps the k largest elements with the smallest of those on top, which is exactly the kth largest.
  3. Partition Direction: When using quickselect for kth largest, the partition must place larger elements on the left (descending order) if you target index k - 1. Alternatively, target index n - k with ascending partition.
  4. Not Randomizing the Pivot: A fixed pivot (e.g., always choosing the first element) degrades quickselect to O(n^2) on sorted or nearly-sorted inputs.
  5. Modifying the Input: Quickselect mutates the array. If the original order must be preserved, make a copy first or use the heap approach.

Interview Tips

  1. Mention All Three Approaches: Show breadth by listing sorting, heap, and quickselect, then compare their complexities.
  2. Implement Quickselect: Interviewers often want to see quickselect because it demonstrates knowledge of partitioning and randomized algorithms.
  3. Discuss Worst Case: Proactively mention that quickselect has O(n^2) worst case but O(n) average with random pivots. Mention that the median-of-medians algorithm guarantees O(n) worst case but is rarely implemented in interviews.
  4. Clarify Constraints: Ask whether you can modify the input array and whether k is always valid.
  5. Follow-up Preparedness: Be ready for variants such as kth smallest, streaming data (use a heap), or finding the median (k = n/2).