Kth Largest Element in an Array

MEDIUM

Description

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

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approaches

Checkout 3 different approaches to solve Kth Largest Element in an Array. Click on different approaches to view the approach and algorithm in detail.

Sorting Approach

Sort the array in descending order and return the kth element.

Algorithm

Sort the array using Arrays.sort()
Return the element at index nums.length - k

This is the most straightforward approach where we sort the array in descending order and return the element at index k-1. While simple to implement, it's not the most efficient solution as it requires sorting the entire array.

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

In this approach, we first sort the array using Java's built-in sorting algorithm (which uses a modified quicksort). After sorting, we return the element at index nums.length - k since the array is sorted in ascending order and we want the kth largest element.

Complexity Analysis

Time Complexity: O(n log n) where n is the length of the array due to sortingSpace Complexity: O(1) as sorting is done in-place in Java's implementation

Pros and Cons

Pros:

Simple to implement
Easy to understand
Uses built-in sorting function

Cons:

Not optimal time complexity
Modifies the original array
Sorts the entire array when we only need the kth largest element

Code Solutions

Checking out 3 solutions in different languages for Kth Largest Element in an Array. Click on different languages to view the code.

class Solution {
public
  int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    return quickSort(nums, 0, n - 1, n - k);
  }
private
  int quickSort(int[] nums, int left, int right, int k) {
    if (left == right) {
      return nums[left];
    }
    int i = left - 1, j = right + 1;
    int x = nums[(left + right) >>> 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(nums, j + 1, right, k);
    }
    return quickSort(nums, left, j, k);
  }
}

Video Solution

Watch the video walkthrough for Kth Largest Element in an Array

Algorithms:

Divide and ConquerSortingQuickselect

Data Structures:

ArrayHeap (Priority Queue)

Companies:

AMD |Accenture |Avito |ByteDance |