Kth Largest Element in a Stream

January 10, 2025

Kth Largest Element in a Stream: Design and Implementation

The Kth Largest Element in a Stream problem requires designing a system to dynamically track the k-th largest integer in a stream of numbers.

This task demands an efficient approach to handle frequent updates while maintaining the k-th largest element in near real-time.

Problem:

Design a class to find the kth largest integer in a stream of values, including duplicates. E.g. the 2nd largest from [1, 2, 3, 3] is 3. The stream is not necessarily sorted.

Implement the following methods:

constructor(int k, int[] nums) Initializes the object given an integer k and the stream of integers nums.
int add(int val) Adds the integer val to the stream and returns the kth largest integer in the stream.

Problem Breakdown

Task

Initialization:
- Create a class KthLargest initialized with:
  - An integer k representing the position of the k-th largest element.
  - An initial array nums that represents the stream of integers.
Dynamic Updates:
- A method add(val) adds a new value to the stream and returns the k-th largest element in the updated stream.

Example 1

["KthLargest", [3, [1, 2, 3, 3]], "add", [3], "add", [5], "add", [6], "add", [7], "add", [8]]

[null, 3, 3, 3, 5, 6]

Explanation:

KthLargest kthLargest = new KthLargest(3, [1, 2, 3, 3]);
kthLargest.add(3); // return 3
kthLargest.add(5); // return 3
kthLargest.add(6); // return 3
kthLargest.add(7); // return 5
kthLargest.add(8); // return 6

Recommended Time & Space Complexity

You should aim for a solution with O(mlogk) time and O(k) space, where m is the number of times add() is called, and k represents the rank of the largest number to be tracked (i.e., the k-th largest element).

Constraints:

1 <= k <= 1000
0 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-1000 <= val <= 1000
There will always be at least k integers in the stream when you search for the kth integer.

Approach

Key Idea: Min-Heap

To efficiently track the k-th largest element, we use a min-heap of size k.

Why Min-Heap?

A min-heap keeps the smallest element at the root.
By maintaining a heap of size k, the root always represents the k-th largest element, as it ensures the heap contains the largest k elements of the stream.

Algorithm

Initialization

Create a min-heap with the first k elements of nums.
If nums has more than k elements, iterate through the remaining numbers and adjust the heap to maintain only the largest k elements.

Add Method

Add the new element val to the heap.
If the heap exceeds size k, remove the smallest element (heap root).
Return the root of the heap, which is the k-th largest element.

Hint 1

A brute force solution would involve sorting the array in every time a number is added using add(), and then returning the k-th largest element. This would take O(m * nlogn) time, where m is the number of calls to add() and n is the total number of elements added. However, do we really need to track all the elements added, given that we only need the k-th largest element? Maybe you should think of a data structure which can maintain only the top k largest elements.

Hint 2

We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes O(logk) time since we are storing k elements in it. Retrieving the top element (the smallest in the heap) takes O(1) time. How can this be useful for finding the k-th largest element?

There are mainly two approach to solve this problem –

Brute Force
Min Heap

1. Sorting

Time complexity: O(m∗nlogn)
Space complexity: or depending on the sorting algorithm.

Python

C++

Java

JavaScript

Python

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.arr = nums

    def add(self, val: int) -> int:
        self.arr.append(val)
        self.arr.sort()
        return self.arr[len(self.arr) - self.k]

C++

class KthLargest {
public:
    vector arr;
    int k;
    KthLargest(int k, vector& nums) {
        this->arr = nums;
        this->k = k;
    }
    
    int add(int val) {
        arr.push_back(val);
        sort(arr.begin(), arr.end());
        return arr[arr.size() - k];
    }
};

Java

class KthLargest {
    List arr;
    int K;
    public KthLargest(int k, int[] nums) {
        K = k;
        arr = new ArrayList();
        for (int i = 0; i < nums.length; i++) {
            arr.add(nums[i]);
        }
    }
    
    public int add(int val) {
        arr.add(val);
        Collections.sort(arr);
        return arr.get(arr.size() - K);
    }
}

JavaScript

class KthLargest {
    /**
     * @param {number} k
     * @param {number[]} nums
     */
    constructor(k, nums) {
        this.arr = nums;
        this.k = k;
    }

    /**
     * @param {number} val
     * @return {number}
     */
    add(val) {
        this.arr.push(val);
        this.arr.sort((a, b) => a - b);
        return this.arr[this.arr.length - this.k];
    }
}

2. Min -Heap

Time & Space Complexity

Time complexity:
Space complexity:

C++

Java

Python

JavaScript

C++

class KthLargest {
private:
    priority_queue, greater> minHeap;
    int k;

public:
    KthLargest(int k, vector& nums) {
        this->k = k;
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
    }

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

Java

class KthLargest {
    
    private PriorityQueue minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

Python

class KthLargest:
    
    def __init__(self, k: int, nums: List[int]):
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        return self.minHeap[0]

JavaScript

/**
 * const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
 */

class KthLargest {
    /**
     * @param {number} k
     * @param {number[]} nums
     */
    constructor(k, nums) {
        this.minHeap = new MinPriorityQueue();
        this.k = k;

        for (const num of nums) {
            this.minHeap.enqueue(num);
        }

        while (this.minHeap.size() > k) {
            this.minHeap.dequeue();
        }
    }

    /**
     * @param {number} val
     * @return {number}
     */
    add(val) {
        this.minHeap.enqueue(val);
        if (this.minHeap.size() > this.k) {
            this.minHeap.dequeue();
        }
        return this.minHeap.front();
    }
}

Where $m$ is the number of calls made to

Unlock this article for Free,
by logging in

Kth Largest Element in a Stream