Kth Largest Element in a Stream

🏠 ⬅️ ➡️

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

Input [ "KthLargest ", "add ", "add ", "add ", "add ", "add "] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8]

Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

Constraints:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth element.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use :: kth_largest_mod
    implicit none

    type(kth_largest) :: kth_largest
    integer :: i, j, k, n
    integer, allocatable :: nums(:)

    ! Example 1
    print *, 'Example 1:'
    k = 3
    allocate(nums(3))
    nums = [4, 5, 8, 2]
    call kth_largest%init(k, nums)
    do i = 1, size(nums)
        print *, kth_largest%add(nums(i))
    end do
    deallocate(nums)

contains

subroutine test()
    use :: kth_largest_mod
    implicit none

    type(kth_largest) :: kth_largest
    integer :: i, j, k, n
    integer, allocatable :: nums(:)

    ! Example 1
    print *, 'Example 1:'
    k = 3
    allocate(nums(3))
    nums = [4, 5, 8, 2]
    call kth_largest%init(k, nums)
    do i = 1, size(nums)
        print *, kth_largest%add(nums(i))
    end do
    deallocate(nums)
end subroutine test

end program main

module kth_largest_mod
    implicit none

    private
    public :: kth_largest

    type :: kth_largest
        private
        integer :: k
        integer, allocatable :: heap(:)
        integer :: heap_size
        logical :: initialized = .false.
    contains
        procedure :: init => init_kth_largest
        procedure :: add => add_to_kth_largest
    end type kth_largest

    interface kth_largest
        module procedure :: init_kth_largest
    end interface kth_largest

contains

subroutine init_kth_largest(this, k, nums)
    class(kth_largest), intent(out) :: this
    integer, intent(in) :: k
    integer, intent(in) :: nums(:)

    if (allocated(this%heap)) then
        deallocate(this%heap)
    end if

    this%k = k
    this%heap_size = 0
    this%initialized = .true.

    call build_heap(this, nums)
end subroutine init_kth_largest

subroutine build_heap(this, nums)
    class(kth_largest), intent(inout) :: this
    integer, intent(in) :: nums(:)
    integer :: i

    do i = 1, size(nums)
        call add_to_heap(this, nums(i))
    end do
end subroutine build_heap

function parent(i) result(parent_index)
    integer, value :: i
    integer :: parent_index

    parent_index = (i + 1) / 2
end function parent

function left(i) result(left_index)
    integer, value :: i
    integer :: left_index

    left_index = 2 * i
end function left

function right(i) result(right_index)
    integer, value :: i
    integer :: right_index

    right_index = 2 * i + 1
end function right

subroutine swap(this, i, j)
    class(kth_largest), intent(inout) :: this
    integer, value :: i, j

    integer :: temp

    temp = this%heap(i)
    this%heap(i) = this%heap(j)
    this%heap(j) = temp
end subroutine swap

subroutine sift_down(this, i)
    class(kth_largest), intent(inout) :: this
    integer, value :: i

    integer :: largest

    largest = i
    if (left(i) <= this%heap_size .and. &
❌ Compiled
❌ Executed
❌ Correct 
module KthLargest
    implicit none

    private
    integer, parameter :: k = 3
    integer, parameter :: n = 4
    integer, parameter :: nums(n) = [4, 5, 8, 2]
    integer, parameter :: vals(n) = [3, 3, 5, 10, 9, 4]
    integer, parameter :: expected(n) = [4, 5, 5, 8, 8]

    type :: KthLargest
        integer :: k
        integer :: max_heap(k)
        integer :: min_heap(k)
        integer :: count = 0
    contains
        procedure, public :: add
    end type KthLargest

contains

    function add(this, val) result(res)
        class(KthLargest), intent(inout) :: this
        integer, intent(in) :: val
        integer :: res

        if (this%count < this%k) then
            this%count = this%count + 1
            this%max_heap(this%count) = val
            this%min_heap(this%count) = val
        else
            if (val > this%max_heap(1)) then
                this%max_heap(1) = val
                call sift_up(this%max_heap, 1)
            else if (val < this%min_heap(1)) then
                this%min_heap(1) = val
                call sift_down(this%min_heap, 1)
            end if
        end if

        res = this%max_heap(1)
    end function add

    recursive subroutine sift_up(arr, i)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: i

        if (i /= 1) then
            if (arr(i) > arr(i/2)) then
                call swap(arr, i, i/2)
                call sift_up(arr, i/2)
            end if
        end if
    end subroutine sift_up

    recursive subroutine sift_down(arr, i)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: i

        if (2*i <= size(arr)) then
            if (arr(i) < arr(2*i)) then
                call swap(arr, i, 2*i)
                call sift_down(arr, 2*i)
            else if (2*i+1 <= size(arr) .and. arr(i) < arr(2*i+1)) then
                call swap(arr, i, 2*i+1)
                call sift_down(arr, 2*i+1)
            end if
        end if
    end subroutine sift_down

    subroutine swap(arr, i, j)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: i, j

        integer :: temp

        temp = arr(i)
        arr(i) = arr(j)
        arr(j) = temp
    end subroutine swap

end module KthLargest

program test_kth_largest
    use KthLargest
    implicit none

    type(KthLargest) :: kth_largest
    integer :: i, res

    do i = 1, size(vals)
        res = kth_largest%add(vals(i))
        write (*,*) res
    end do

end program test_kth_largest
🌐 Data from online sources 
import heapq

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_heap = nums
        heapq.heapify(self.min_heap)

        while len(self.min_heap) > k:
            heapq.heappop(self.min_heap)

    def add(self, val: int) -> int:
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, val)
        elif val > self.min_heap[0]:
            heapq.heappushpop(self.min_heap, val)
        return self.min_heap[0]

We will use a min-heap to solve this problem. We initialize the KthLargest class with an integer k and an array nums. In the constructor, we loop through the nums array and call the add function for every element.

The add function does the following: 1. Pushes the new value into the min-heap. 2. If the size of the min-heap is greater than k, we pop an element from the min-heap (i.e., remove the smallest element). 3. We return the top element of the min-heap which represents the k-th largest element in the stream.

For the JavaScript implementation, we also need to create a separate MinHeap class covering the basic functions (offer, poll, peek, size) to maintain minimum priority queue.

All implementations follow the same algorithm, with small syntax differences between programming languages.

🌐 Data from online sources 
#include <queue>
#include <vector>

class KthLargest {
public:
    int k;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    KthLargest(int k, std::vector<int>& nums) {
        this->k = k;
        for (int num : nums) {
            add(num);
        }
    }

    int add(int val) {
        minHeap.push(val);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
        return minHeap.top();
    }
};

We will use a min-heap to solve this problem. We initialize the KthLargest class with an integer k and an array nums. In the constructor, we loop through the nums array and call the add function for every element.

The add function does the following: 1. Pushes the new value into the min-heap. 2. If the size of the min-heap is greater than k, we pop an element from the min-heap (i.e., remove the smallest element). 3. We return the top element of the min-heap which represents the k-th largest element in the stream.

For the JavaScript implementation, we also need to create a separate MinHeap class covering the basic functions (offer, poll, peek, size) to maintain minimum priority queue.

All implementations follow the same algorithm, with small syntax differences between programming languages.