Level Order

 source code

Kth largest element

Find the k-th largest element in an array of values

[1, 2, 3, 5, 4]

When k = 1, the 1st largest element is 5
When k = 3, the 3rd largest element is 3
Solution Time Space
Sorting O(n log n) O(1) to O(n)
Min-heap O(n + k log n) O(n)
Max-heap O(n log k) O(k)
Quickselect O(n) to O(n2) O(log n) to O(n)
Median of medians O(n) O(log n)

Solution 1: Sorting

To find the k-th largest value:

  • Sort the input array of values
  • Look at array index n-k in the sorted array
  • This is the k-th largest value

Sorting the entire array is fine when n is small, but fully sorting the array is doing a lot of unnecessary work when all we want is to find a single number. Plus you would want more-efficient solutions when n is large.

def kth_largest_element(values, k)
  values.sort![-k]
end
Time O(n log n) Average time complexity for sorting n numbers
Space O(1) to O(n) Varies depending on the sorting algorithm

Solution 2: Max-heap

To find the k-th largest value:

  • Insert all the elements in the array into a max-heap
  • Pop from the heap k times
  • The k-th value popped is the k-th largest value

Runtime analysis:

  • Building a max heap takes O(n) time and O(n) space
  • Finding the max element in the heap takes O(1) time
  • Removing the max element and fixing heap order takes O(log n) time
  • Removing the max element k times takes O(k log n) time overall

Looking at different values of k:

  • When k = n, the time complexity is O(n + n log n) ~ O(n log n)
  • When k = 1, the time complexity is O(n + 1 log n) ~ O(n)
require 'max_heap'

def kth_largest_element(values, k)
  heap = MaxHeap.new(values)
  kth_largest = nil
  k.times do
    kth_largest = heap.pop
  end
  kth_largest
end
Time O(n + k log n) O(n) to build the heap + k pops at O(log n) each
Space O(n) n elements in the heap

Solution 3: Min-heap

Alternatively, we can use a min heap to save space and for the opposite trend in time complexity as the value of k changes.

To find the k-th largest value:

  • Create a min-heap with a max size of k
  • For each element in the array
    • If the heap is not yet full, put it into the heap
    • If the heap is full, add it if it's larger than the min value in the heap
  • Each of n insertions will take O(log k) time
  • The min value in the heap is the kth-largest element
  • Looking at the min value in a min heap takes O(1) time
Time O(n log k) n insertions into a k-sized heap take O(log k) time each
Space O(k) k elements in the heap

Solution 4: Quickselect

Quickselect is a popular selection algorithm that finds the kth-smallest element in O(n) time on average.

By only partially sorting the array, we can avoid doing unnecessary work.

To find the k-th largest value:

  • Note that the kth-smallest value is the (n-k+1)th largest
    • You know the array index of the value you're looking for
  • Apply quickselect, which works like this:
    • Choose a random element in the array as a pivot
    • Move every element smaller than the pivot to the left of the pivot
    • You now have an array where
      • You know the index of the pivot
      • The pivot is in the correct sorted position
      • Every value left of the pivot is smaller
      • Every value right of the pivot is larger than or equal to it
    • Compare the index of the pivot to the index you're looking for
      • If it's equal, you've found the kth-largest value
      • If it's smaller, quickselect the upper partition of the array
      • If it's larger, quickselect the bottom partition of the array
def kth_largest_element(values, k)
  n = values.length
  quickselect(values, 0, n-1, n-k)
end

def quickselect(values, low, high, i_target)
  return values[low] if low == high
  i = partition(values, low, high)
  if i == i_target
    values[i]
  elsif i < i_target
    quickselect(values, i + 1, high, i_target)
  else
    quickselect(values, low, i - 1, i_target)
  end
end

def partition(values, low, high)
  i_pivot = (low + (high - low)*rand).to_i
  pivot = values[i_pivot]
  values[high], values[i_pivot] = values[i_pivot], values[high]
  j = low
  (low .. high).each do |i|
    if values[i] < pivot
      values[i], values[j] = values[j], values[i]
      j += 1
    end
  end
  values[j], values[high] = values[high], values[j]
  j
end
Time O(n) to O(n2) Worst case O(n2) if you get unlucky
Space O(log n) to O(n) Recursion stack depth, worst case O(n)

Solution 5: Median of medians

The previous solution used quickselect with random pivots, which randomly has poor worst-case if you get unlucky and select a bunch of bad pivots.

By improving the way that pivots are chosen, we eliminate the possibility of running into the worst-case performance scenario. The tradeoff is that we'll do slightly more work on average, but still in linear time.

Time O(n)
Space O(log n) Recursion stack depth

Resources