Solutions

1. Sorting

O(nlogn) time | O(1) space

Intuition

We can sort the array from largest to smallest, which puts the kth largest element in the kth position.

Algorithm

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

k = 2

012345

sort the array

1 / 3

Code

def findKthLargest(nums: list[int], k: int) -> int:
    nums.sort(reverse=True)
    return nums[k - 1]

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number}
 */
var findKthLargest = function (nums, k) {
  nums.sort((a, b) => b - a)
  return nums[k - 1]
}

import java.util.Arrays;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        reverse(nums);
        return nums[k - 1];
    }

    private void reverse(int[] nums) {
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            int held = nums[i];
            nums[i] = nums[j];
            nums[j] = held;
        }
    }
}

2. Min Heap

O(nlogk) time | O(k) space

Intuition

We can keep a heap of only the k largest elements seen so far, smallest on top, so whatever is on top at the end is the kth largest.

Algorithm

Create an empty min heap.
Traverse through the elements.
- Push the element onto the heap.
- Pop the top when the heap holds more than k elements.
Return the top of the heap.

k = 2

push 3

1 / 11

Code

import heapq


def findKthLargest(nums: list[int], k: int) -> int:
    largest = []
    for value in nums:
        heapq.heappush(largest, value)
        if len(largest) > k:
            heapq.heappop(largest)
    return largest[0]

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number}
 */
var findKthLargest = function (nums, k) {
  const largest = new MinPriorityQueue()
  for (const value of nums) {
    largest.push(value)
    if (largest.size() > k) largest.pop()
  }
  return largest.top()
}

class MinPriorityQueue {
  constructor() {
    this.values = []
  }

  size() {
    return this.values.length
  }

  top() {
    return this.values[0]
  }

  push(value) {
    this.values.push(value)
    let at = this.values.length - 1
    while (at > 0) {
      const parent = (at - 1) >> 1
      if (this.values[parent] <= this.values[at]) break
      this.swap(parent, at)
      at = parent
    }
  }

  pop() {
    const top = this.values[0]
    this.values[0] = this.values[this.values.length - 1]
    this.values.pop()
    let at = 0
    for (;;) {
      let smallest = at
      for (const child of [at * 2 + 1, at * 2 + 2]) {
        if (child < this.values.length && this.values[child] < this.values[smallest]) smallest = child
      }
      if (smallest === at) return top
      this.swap(smallest, at)
      at = smallest
    }
  }

  swap(a, b) {
    const held = this.values[a]
    this.values[a] = this.values[b]
    this.values[b] = held
  }
}

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> largest = new PriorityQueue<>();
        for (int value : nums) {
            largest.offer(value);
            if (largest.size() > k) largest.poll();
        }
        return largest.peek();
    }
}

3. Quick Select

O(n) time on average, O(n²) at worst | O(1) space

Intuition

We can take any number as the pivot, partition the array putting elements greater than the pivot to the left, and smaller than the pivot to the right.

This way the pivot ends up at the index as in the sorted array. We can tell on which side the target is and do the partition again on that side.

Algorithm

Create a partition function taking the input array, and the low and high indexes.
- Take the last element of the slice as the pivot, and start a j index at low.
- Iterate through the slice with an i index, swapping the element at i to j and moving j on whenever that element is greater than the pivot.
- Swap the pivot to j and return j.
Traverse through the array with a low and a high bound, starting at the first and the last element.
- Call partition with low and high, which returns the index the pivot landed on.
- Return the element at that index when it is k - 1.
- Move low past the pivot when the pivot index is less than k - 1, and move high before the pivot otherwise.
Return the element at low once the two bounds meet.

k = 2

012345

take 4 as a pivot, 3 < 4, belongs right

1 / 11

Code

def findKthLargest(nums: list[int], k: int) -> int:
    low = 0
    high = len(nums) - 1
    while low < high:
        pivot = partition(nums, low, high)
        if pivot == k - 1:
            return nums[pivot]
        if pivot < k - 1:
            low = pivot + 1
        else:
            high = pivot - 1
    return nums[low]


def partition(nums: list[int], low: int, high: int) -> int:
    j = low
    for i in range(low, high):
        if nums[i] > nums[high]:
            nums[i], nums[j] = nums[j], nums[i]
            j += 1
    nums[j], nums[high] = nums[high], nums[j]
    return j

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number}
 */
var findKthLargest = function (nums, k) {
  let low = 0
  let high = nums.length - 1
  while (low < high) {
    const pivot = partition(nums, low, high)
    if (pivot === k - 1) return nums[pivot]
    if (pivot < k - 1) low = pivot + 1
    else high = pivot - 1
  }
  return nums[low]
}

function partition(nums, low, high) {
  let j = low
  for (let i = low; i < high; i++) {
    if (nums[i] > nums[high]) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
      j++
    }
  }
  ;[nums[j], nums[high]] = [nums[high], nums[j]]
  return j
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = partition(nums, low, high);
            if (pivot == k - 1) return nums[pivot];
            if (pivot < k - 1) low = pivot + 1;
            else high = pivot - 1;
        }
        return nums[low];
    }

    private int partition(int[] nums, int low, int high) {
        int j = low;
        for (int i = low; i < high; i++) {
            if (nums[i] > nums[high]) swap(nums, i, j++);
        }
        swap(nums, j, high);
        return j;
    }

    private void swap(int[] nums, int a, int b) {
        int held = nums[a];
        nums[a] = nums[b];
        nums[b] = held;
    }
}