703. Kth Largest Element in a Stream

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: ["KthLargest", "add", "add", "add", "add", "add"][[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output: [null, 4, 5, 5, 8, 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.

Solution Approach

This solution involves maintaining a sorted list of elements, where each new element is inserted at the correct position using binary search, allowing efficient retrieval of the kth largest element in the stream.

Algorithm

1. Maintain Sorted Order: The list is kept sorted at all times by inserting each new value in the correct position using binary search.
2. Insert Efficiently: Use binary search (bisect_left) to determine the correct insertion point for the new value, ensuring that the list remains sorted.
3. Retrieve kth Largest: After inserting a new value, the kth largest element is always at index -self.k in the sorted list, providing efficient access to the desired element.

Implement

    class KthLargest: def __init__(self, k: int, nums: List[int]):
    self.k = k
    self.nums = nums
    self.nums.sort()

def add(self, val: int) -> int:
    l, r = 0, len(self.nums) - 1
    while l <= r:
        m = l + (r - l) // 2
        if self.nums[m] < val:
            l = m + 1
        else:
            r = m + 1
    self.nums.insert(l, val)
    return self.nums[-self.k]

# def __init__(self, k: int, nums: List[int]): #     self.k = k #     self.nums = sorted(nums)
# def add(self, val: int) -> int: #     insert_position = bisect.bisect_left(self.nums, val) #     self.nums.insert(insert_position, val) #     return self.nums[-self.k]

    
    

Twitter  facebook  Email