Solutions

# Sorting every time, or binary search and insert, or min heap.
# heap

# Sorting: time O(m * nlogn), space O(n + m)
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]

# Binary search on insert: time O(m * log n), space(n + m)
class KthLargest:

    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.stream = nums
        self.stream.sort()

    def add(self, val: int) -> int:
        index = self.getIndex(val)
        # Add val to correct position
        self.stream.insert(index, val)
        return self.stream[-self.k]

    def getIndex(self, val: int) -> int:
        left, right = 0, len(self.stream) - 1
        while left <= right:
            mid = left + (right - left) // 2
            mid_element = self.stream[mid]
            if mid_element == val:
                return mid
            elif mid_element > val:
                right = mid - 1
            else:
                left = mid + 1
        return left

# Min heap: time O(m log k), space O(k)
import heapq

class KthLargest:

    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

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