Saturday, February 18, 2023

Kth largest element in an array

Leetcode 215 problem.

A function, given an integer array nums and an integer k, to return the kth largest element in the array.


  • Time complexity: O(klog(n))O(k*log(n)) - n is a quantity of numbers, k is a quantity of numbers to return
  • Auxiliary space: O(1)O(1) - constant amount of space
import "fmt"

import "container/heap"

type MinHeap []int

// first is smaller than second
func (hp MinHeap) Less(i, j int) bool {
    return hp[i] < hp[j]

func (hp MinHeap) Swap(i, j int) {
    hp[i], hp[j] = hp[j], hp[i]

func (hp MinHeap) Len() int {
    return len(hp)

// simple appending to the same memory address
func (hp *MinHeap) Push(x interface{}) {
    *hp = append(*hp, x.(int))

func (hp *MinHeap) Pop() interface{} {
    oldHeap := *hp
    oldLength := len(oldHeap)

    // get and remove last element from heap
    item := oldHeap[oldLength-1]
    *hp = oldHeap[:oldLength-1]

    return item

func findKthLargest(nums []int, k int) int {
    hp := MinHeap{}

    // pop all till Kth element
    for _, num := range nums {
        heap.Push(&hp, num)

        if (len(hp) > k) {

    // pop Kth element
    return heap.Pop(&hp).(int)
Creative Commons Licence