101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Brute Force Approach - Complex approach
  2. Min Heap Approach - Complex approach

Approach 1: Brute Force Approach

Let's start by understanding the problem: we need to design a class that finds the kth largest element in a stream of numbers.

Thinking Process: The most straightforward approach is to maintain a sorted list of all elements in the stream. When a new element is added, we insert it into the correct position to maintain the sorted order, and then return the kth largest element.

For the constructor, we initialize the class with the given array and sort it in descending order. For the add method, we insert the new element into the correct position in the sorted array and return the kth element from the beginning.

Intuition: This approach directly follows the problem statement. We maintain a sorted list and return the kth element. However, it's not the most efficient approach, especially for large streams, as inserting an element into a sorted array takes O(n) time.

Algorithm:

  1. Initialize the class with the given array and sort it in descending order.
  2. For the add method:
  3. a. Insert the new element into the correct position in the sorted array.
  4. b. Return the kth element from the beginning of the array.

Time Complexity:

O(n) for add operation

Where n is the number of elements in the stream. Inserting an element into a sorted array takes O(n) time in the worst case, as we may need to shift all elements.

Space Complexity:

O(n)

We need to store all elements in the stream, which takes O(n) space.

Approach 2: Min Heap Approach

We can optimize the previous approach by using a min heap (priority queue) of size k to maintain the k largest elements.

Thinking Process: Instead of maintaining a sorted list of all elements, we only need to keep track of the k largest elements. We can use a min heap of size k for this purpose. The smallest element in the heap (the root) will be the kth largest element in the stream.

For the constructor, we initialize a min heap and add all elements from the given array. If the heap size exceeds k, we remove the smallest element. For the add method, we add the new element to the heap and remove the smallest element if the heap size exceeds k. The root of the heap will be the kth largest element.

Intuition: A min heap of size k allows us to efficiently maintain the k largest elements in the stream. The smallest element in the heap (the root) will be the kth largest element in the stream. This approach is more efficient than the brute force approach, especially for large streams.

Algorithm:

  1. Initialize a min heap.
  2. Add all elements from the given array to the heap.
  3. If the heap size exceeds k, remove the smallest element.
  4. For the add method:
  5. a. Add the new element to the heap.
  6. b. If the heap size exceeds k, remove the smallest element.
  7. c. Return the root of the heap (the kth largest element).

Time Complexity:

O(log k) for add operation

Adding an element to a heap takes O(log k) time, where k is the size of the heap. Since our heap size is limited to k, the time complexity is O(log k).

Space Complexity:

O(k)

We only need to store k elements in the heap, which takes O(k) space.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
class KthLargest:
    function __init__(k, nums):
        this.k = k
        this.nums = sort nums in descending order
    
    function add(val):
        insert val into the correct position in this.nums to maintain sorted order
        return this.nums[k-1]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone