Kth Largest Element in Array

Find the kth largest element in an unsorted array

Language Selection

Choose your preferred programming language

Showing: Python

Kth Largest Element in 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.

You must solve it in O(n) time complexity.

Input/Output Specifications

Input:
- nums: Array of integers
- k: Integer (1 <= k <= nums.length)
Output: Integer representing the kth largest element

Constraints

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

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.

Solution Approaches

Approach 1: Min-Heap (Priority Queue) - Good for Small K

Algorithm Explanation:

Use a min-heap of size k to maintain the k largest elements
Iterate through array:
- If heap size < k, add element
- If element > heap top, remove top and add element
Return heap top (kth largest element)

Implementation:

Python:

import heapq

def find_kth_largest_heap(nums, k):
    """
    Find kth largest element using min-heap
    Time: O(n log k)
    Space: O(k)
    """
    min_heap = []
    
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    
    return min_heap[0]  # kth largest element

# Alternative using heapq.nlargest
def find_kth_largest_builtin(nums, k):
    """
    Find kth largest using built-in function
    Time: O(n log k)
    Space: O(k)
    """
    return heapq.nlargest(k, nums)[-1]

Java:

import java.util.*;

class Solution {
    /**
     * Find kth largest element using min-heap
     * Time: O(n log k)
     * Space: O(k)
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        
        return minHeap.peek();
    }
}

Go:

import (
    "container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// findKthLargest - Find kth largest element using min-heap
// Time: O(n log k), Space: O(k)
func findKthLargest(nums []int, k int) int {
    minHeap := &MinHeap{}
    heap.Init(minHeap)
    
    for _, num := range nums {
        if minHeap.Len() < k {
            heap.Push(minHeap, num)
        } else if num > (*minHeap)[0] {
            heap.Pop(minHeap)
            heap.Push(minHeap, num)
        }
    }
    
    return (*minHeap)[0]
}

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }
    
    peek() {
        return this.heap[0];
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let minChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] < this.heap[minChildIdx]) {
                minChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] <= this.heap[minChildIdx]) break;
            [this.heap[idx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[idx]];
            idx = minChildIdx;
        }
    }
}

/**
 * Find kth largest element using min-heap
 * Time: O(n log k)
 * Space: O(k)
 */
function findKthLargest(nums, k) {
    const minHeap = new MinHeap();
    
    for (const num of nums) {
        if (minHeap.size() < k) {
            minHeap.push(num);
        } else if (num > minHeap.peek()) {
            minHeap.pop();
            minHeap.push(num);
        }
    }
    
    return minHeap.peek();
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find kth largest element using min-heap
    /// Time: O(n log k)
    /// Space: O(k)
    /// </summary>
    public int FindKthLargest(int[] nums, int k) {
        var minHeap = new PriorityQueue<int, int>();
        
        foreach (int num in nums) {
            if (minHeap.Count < k) {
                minHeap.Enqueue(num, num);
            } else if (num > minHeap.Peek()) {
                minHeap.Dequeue();
                minHeap.Enqueue(num, num);
            }
        }
        
        return minHeap.Peek();
    }
}

Approach 2: Quickselect (Optimal - O(n) Average)

Algorithm Explanation:

Use quickselect algorithm to find kth largest element
Partition array around pivot, placing larger elements on left
Recursively search in appropriate partition
Return element when partition index equals k-1

Implementation:

Python:

import random

def find_kth_largest_quickselect(nums, k):
    """
    Find kth largest element using quickselect
    Time: O(n) average, O(n²) worst case
    Space: O(1)
    """
    def quickselect(left, right, k_smallest):
        """Find k-th smallest element in nums[left:right+1]"""
        if left == right:
            return nums[left]
        
        # Random pivot for better average performance
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return quickselect(left, pivot_index - 1, k_smallest)
        else:
            return quickselect(pivot_index + 1, right, k_smallest)
    
    def partition(left, right, pivot_index):
        """Partition array for quickselect (descending order for kth largest)"""
        pivot_value = nums[pivot_index]
        
        # Move pivot to end
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        
        # Partition: larger elements go to left
        store_index = left
        for i in range(left, right):
            if nums[i] > pivot_value:
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        
        # Move pivot to final position
        nums[right], nums[store_index] = nums[store_index], nums[right]
        return store_index
    
    # Convert kth largest to (k-1)th in 0-indexed array sorted in descending order
    return quickselect(0, len(nums) - 1, k - 1)

# Iterative version
def find_kth_largest_quickselect_iterative(nums, k):
    """
    Iterative quickselect implementation
    Time: O(n) average, O(n²) worst case
    Space: O(1)
    """
    def partition(left, right, pivot_index):
        pivot_value = nums[pivot_index]
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        
        store_index = left
        for i in range(left, right):
            if nums[i] > pivot_value:  # For kth largest
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        
        nums[right], nums[store_index] = nums[store_index], nums[right]
        return store_index
    
    left, right = 0, len(nums) - 1
    k_smallest = k - 1
    
    while left <= right:
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            right = pivot_index - 1
        else:
            left = pivot_index + 1
    
    return -1  # Should never reach here

Approach 3: Sorting (Simple but Not Optimal)

Algorithm Explanation:

Sort the array in descending order
Return element at index k-1

Implementation:

Python:

def find_kth_largest_sorting(nums, k):
    """
    Find kth largest using sorting
    Time: O(n log n)
    Space: O(1) if in-place sort allowed
    """
    nums.sort(reverse=True)
    return nums[k - 1]

Key Insights

Min-Heap Strategy: Maintain k largest elements, root is kth largest
Quickselect Efficiency: Average O(n) but worst-case O(n²)
Random Pivot: Improves quickselect average performance
Partitioning: For kth largest, partition with larger elements on left

Edge Cases

k = 1: Return maximum element
k = n: Return minimum element
Single Element: Array with one element
Duplicate Values: Multiple occurrences of kth largest
All Same Values: All elements identical

Test Cases

def test_find_kth_largest():
    # Basic test cases
    assert find_kth_largest_heap([3,2,1,5,6,4], 2) == 5
    assert find_kth_largest_heap([3,2,3,1,2,4,5,5,6], 4) == 4
    
    # Edge cases
    assert find_kth_largest_heap([1], 1) == 1
    assert find_kth_largest_heap([1,2], 1) == 2
    assert find_kth_largest_heap([1,2], 2) == 1
    
    # All same values
    assert find_kth_largest_heap([5,5,5,5], 2) == 5
    
    # Negative numbers
    assert find_kth_largest_heap([-1,-3,2,0,1], 2) == 1
    
    # Test quickselect as well
    assert find_kth_largest_quickselect([3,2,1,5,6,4], 2) == 5
    assert find_kth_largest_quickselect([3,2,3,1,2,4,5,5,6], 4) == 4
    
    print("All tests passed!")

test_find_kth_largest()

Interview Tips

Ask About Constraints: Is k always valid? Can we modify input array?
Discuss Trade-offs: Heap vs quickselect vs sorting
Mention Optimization: Random pivot for quickselect
Handle Edge Cases: k=1, k=n, duplicates, single element
Follow-up Questions: Be ready to implement both heap and quickselect

Follow-up Questions

Kth Smallest Element: Modify for finding kth smallest
Streaming Data: Handle continuous stream of numbers
Memory Constraint: What if only O(1) extra space allowed?
Multiple Queries: Multiple k values for same array
Distinct Elements: Find kth largest distinct element

Common Mistakes

Wrong Heap Type: Using max-heap instead of min-heap
Index Confusion: Off-by-one errors with k and array indices
Partition Logic: Wrong comparison in quickselect partition
Worst Case: Not considering O(n²) worst case of quickselect
Duplicate Handling: Not handling duplicate values correctly

Concept Explanations

Why Min-Heap for Kth Largest: A min-heap of size k maintains the k largest elements seen so far. The root (minimum of these k elements) is exactly the kth largest element overall.

Quickselect Algorithm: Based on quicksort partitioning but only recurses into one side. For kth largest, we partition so that larger elements are on the left, then search accordingly.

Time Complexity Analysis:

Heap: O(n log k) - each element processed once with O(log k) heap operations
Quickselect: O(n) average - each recursion eliminates roughly half the elements
Sorting: O(n log n) - standard comparison-based sorting bound

When to Apply: Use heap approach when k is small relative to n. Use quickselect when you need guaranteed O(n) average performance and can modify the input array. Use sorting when simplicity is preferred and O(n log n) is acceptable.