Skip to content

215.kth-largest-element-in-an-array.md

Latest commit

 

History

History
209 lines (177 loc) · 6.09 KB

215.kth-largest-element-in-an-array.md

File metadata and controls

209 lines (177 loc) · 6.09 KB

215. Kth Largest Element in an Array

Clarification Questions

  • Is the array sorted?
  • Is k always valid? Within the range of 1 to the size of array?

Test Cases

Normal Cases

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

Edge / Corner Cases

  • Some or all are duplicate values.
Input: nums = [8,8,8,8,8,8,8,8], k = 4
Output: 8

Input: nums = [1,2,1,2], k = 4
Output: 2
  • k is the first or last element.
Input: nums = [1,2,3], k = 1 or 3
Output: 1 or 3

Sorting

  • Sort the array in descending order, then return the k-1-th element.

Max Heap (Built-in)

We can build a max heap, then pop k-1 elements, the top element is the k-th largest element.

fun findKthLargest(nums: IntArray, k: Int): Int {
    // Default is ascending
    val heap = PriorityQueue<Int>() { n1, n2 -> n2 - n1 }
    heap.addAll(nums.toList())
    for (i in 1 until k) heap.poll()
    return heap.peek()
}
  • Time Complexity: O(n + k * log n) = O(n log n)
  • Space Complexity: O(n).

Min Heap (Built-in)

We maintains min heap of size k, we iterate the array and add the element to the heap, if the heap size is greater than k, we poll the top element. The top element is the k-th largest element.

fun findKthLargest(nums: IntArray, k: Int): Int {
    val minHeap = PriorityQueue<Int>()
    for (num in nums) {
        minHeap.add(num)
        if (minHeap.size > k) minHeap.poll()
    }
    return minHeap.peek()
}
  • Time Complexity: O(k * log k).
  • Space Complexity: O(k).

Heap (Self-implemented)

The same idea as the built-in heap, but we can implement it by ourselves. It's important to use heapSize for heapify() and pop(), the heap size varies from the two function and you can't change the array.

Or use the full implementation from the heap.md.

fun findKthLargest(nums: IntArray, k: Int): Int {
    var heapSize = nums.size
    buildMaxHeap(nums)
    // Pop k - 1 item, then the k-th is the answer
    for (i in 1 until k) {
        pop(nums, heapSize--)
    }
    return nums[0]
}

private fun buildMaxHeap(A: IntArray) {
    for (i in A.size / 2 downTo 0) {
        heapifyDown(A, i, A.size) 
    }
}

// heapSize is used to check out of bound
private fun heapifyDown(A: IntArray, index: Int, heapSize: Int) {
    val leftIndex = index * 2 + 1
    val rightIndex = index * 2 + 2
    var largestIndex = index
    
    if (leftIndex < heapSize && A[leftIndex] > A[largestIndex]) {
        largestIndex = leftIndex
    }
    if (rightIndex < heapSize && A[rightIndex] > A[largestIndex]) {
        largestIndex = rightIndex
    }
    if (largestIndex != index) {
        swap(A, largestIndex, index)
        heapifyDown(A, largestIndex, heapSize)
    }
}

private fun swap(A: IntArray, i: Int, j: Int) {
    val temp = A[i]
    A[i] = A[j]
    A[j] = temp
}

// We pop the item from array, but we don't actually remove it from array, just decrease the heap size
private fun pop(A: IntArray, heapSize: Int): Int {
    val peek = A[0]
    A[0] = A[heapSize - 1]
    heapifyDown(A, 0, heapSize - 1)
    return peek
}

NOTE!! The k-th element from the array A after buildMaxHeap() CAN'T be accessed directed by A[k - 1], it should be accessed by poll() (it will re-heapify after this operation). See the below example:

Original = [3,2,3,1,2,4,5,5,6]
Heap = [6,5,5,3,2,4,3,2,1]
// kth = 4 is not 3!!!
  • Time Complexity: O(n + k * log n) = O(n log n)
  • Space Complexity: O(log n) for recurcively calling heapifyDown().

Quickselect

Nice explanation: https://leetcode.com/problems/top-k-frequent-elements/editorial/#approach-2-quickselect-hoares-selection-algorithm

The Idea from Quick Sort, We keep partitioning the array to the distribution [ < X ][X][ > X] until the pivot index is the k-th element.

fun findKthLargest(nums: IntArray, k: Int): Int {
    // Top k = (size - k)-th small number
    // Quick sort is sort ascendingly, we have find the (size - k)-th small number!!
    return quickSelect(nums, 0, nums.size - 1, nums.size - k)
    // Or
    // We can use k - 1 (0-based) when `partition()` use `>` pivot to compare (sort descending)
    // return quickSelect(nums, 0, nums.size - 1, k - 1)
}

private fun quickSelect(nums: IntArray, start: Int, end: Int, k: Int): Int {
    val pivotIndex = partition(nums, start, end)
    if (pivotIndex == k) return nums[pivotIndex]
    else {
        return if (pivotIndex < k) quickSelect(nums, pivotIndex + 1, end, k)
        else quickSelect(nums, start, pivotIndex - 1, k)
    }
}

private fun partition(nums: IntArray, start: Int, end: Int): Int {
    val randomIndex = (Math.random() * (end - start + 1)).toInt()
    nums.swap(start, start + randomIndex)
    var pivot = nums[start]
    var i = start
    for (j in start + 1..end) {
        if (nums[j] < pivot) { // Alternative: We use nums[j] > pivot for descending order
            i++
            nums.swap(i, j)
        }
    }
    nums.swap(i, start)
    return i
}

private fun swap(A: IntArray, i: Int, j: Int) {
    val temp = A[i]
    A[i] = A[j]
    A[j] = temp
}
  • Time Complexity: Average O(n) (worst case O(n^2)), where n is the size of array.
  • Space Complexity: O(log n) (averaged) for recursion, but O(n^2) for worst case.

Dry Run

We choose A[start] as the pivot, and we don't choose random index for the pivot in the dry run.

Input: nums = [3, 1, 2], k = 2

index: 0, 1, 2
value: 3, 1, 2
quickSelect(start = 0, end = 2, k = 1)
    pivotIndex = partition(start = 0, end = 2) // 3, 1, 2
        [3, 1, 2]
         p          // We assuem A[start] is the pivot, no random index
               i 
               j
        [2, 1, 3]  
               p
    pivotIndex = 2

index: 0, 1, 2
value: 2, 1, 3
quickSelect(start = 0, end = 1, k = 1)
    pivotIndex = partition(start = 0, end = 1) // 2, 1
        [2, 1]
         p
            i
            j
        [1, 2]
         p
    pivotIndex = 1

return 2 // 2 is the 2nd largest element