#215 Kth Largest Element in an Array - Solution

The goal of #215 Kth Largest Element in an Array is to find the element that appears in the kth position when the array is ordered from largest to smallest. A straightforward idea is to sort the array and directly access the element at index n - k. While simple, sorting costs O(n log n) time.

A more efficient interview-friendly approach uses a min-heap (priority queue) of size k. By keeping only the largest k elements in the heap, the root always represents the kth largest value. This reduces the time complexity to O(n log k) with O(k) space.

For optimal performance, many candidates use the Quickselect algorithm, a divide-and-conquer technique related to quicksort. It partitions the array around a pivot and recursively focuses only on the relevant side, achieving an average time complexity of O(n) and constant extra space.

Approach	Time Complexity	Space Complexity
Sorting	O(n log n)	O(1) or O(n) depending on sort
Min Heap (size k)	O(n log k)	O(k)
Quickselect	Average: O(n), Worst: O(n^2)	O(1)

Solutions (11)

Using a Min-Heap (Priority Queue)

By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the k^th largest element.

Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.

C C++Java Python C#JavaScript

1using System;
2using System.Collections.Generic;
3
4class KthLargestElement {
5    static int FindKthLargest(int[] nums, int k) {
6        SortedSet<(int, int)> minHeap = new SortedSet<(int, int)>();
7        foreach (int num in nums) {
8            minHeap.Add((num, num));
9            if (minHeap.Count > k) {
10                minHeap.Remove(minHeap.Min);
11            }
12        }
13        return minHeap.Min.Item1;
14    }

    static void Main() {
        int[] nums = {3,2,1,5,6,4};
        int k = 2;
        Console.WriteLine(FindKthLargest(nums, k));
    }
}

Explanation

Using C# SortedSet to simulate a min-heap by storing elements as tuples of `(num, num)` to handle duplicates. Maintain a size of k elements by removing the smallest element once the set exceeds k elements. The smallest element remaining is the k^th largest.

Quickselect Algorithm

Quickselect is an efficient selection algorithm to find the k^th smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.

Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.

C C++Java Python C#

1#include <iostream>
#include <vector>
#include <algorithm>

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] > pivot) {
            std::swap(nums[i++], nums[j]);
        }
    }
    std::swap(nums[i], nums[right]);
    return i;
}

int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left < right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) return nums[pivotIndex];
        else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
        else return quickSelect(nums, left, pivotIndex - 1, k);
    }
    return nums[left]; // if left == right
}

int findKthLargest(std::vector<int>& nums, int k) {
    return quickSelect(nums, 0, nums.size() - 1, k - 1);
}

int main() {
    std::vector<int> nums = {3,2,1,5,6,4};
    int k = 2;
    std::cout << findKthLargest(nums, k) << std::endl;
    return 0;
}