To solve this problem, you need to find the kth smallest element many times.

To do this optimally, you should realize that each time you call getKthSmallest(), many of the numbers will be the same. For example, here are typical numbers that you might track over time:

# tracked numbers over time
# 4, 1
# 4, 1, 1, 2
# 4, 1, 1, 2, 3
# 4, 1, 1, 2, 3, 3
# 4, 1, 1, 2, 3, 3, 5

Since many of the same numbers appear each time, you should be able to optimize by remembering something about your past computations.

It's not obvious at first (see below for other solutions), but in this problem you can use a Heap data structure to remember past computations. To do this, you can use a Max-Heap that contains the $k$ smallest numbers you've seen so far. This lets you find the kth smallest number quickly - it's the root node of the heap. It also lets you add numbers quickly.

Here's an example maxheap, where k=6:

When we first create the object, we should store the Heap maxheap, and the size of the heap k for later. Here's the code for doing this:

def __init__(self, k):
    # store `maxheap` and `k` for later
    self.maxheap = []
    self.k = k

We can now write the add function. When we add a new number, we need to update the maxheap so that it has the k smallest elements in it. Here's the code for this:

def add(self, num):

    k, maxheap = self.k, self.maxheap

    # if heap has fewer than `k` elements, add `num` to heap
    if len(maxheap) < k:
        heapq.heappush(maxheap, -num)
    
    # else if `num` is smaller than any of the elements in the heap, then replace it out for the root node of the heap
    elif num > maxheap[0]: 
        heapq.heappop(maxheap)
        heapq.heappush(maxheap, -num)


    # Python doesn't have a Max-Heap, so we implement it using a Min-Heap
    # to do this, you negate each value when you add/remove it

Now we've created and updated the heap. We can get the kth smallest element, by looking at the root node of the heap:

def getKthSmallest(self):
    return -self.maxheap[0] # negative since maxheap

Here's the full solution, putting all of the above code together:

import heapq

class KthSmallestTracker:

    def __init__(self, k):
        self.k = k
        self.maxheap = []


    def add(self, num):
        k, maxheap = self.k, self.maxheap

        # add `num` to heap
        if len(maxheap) < k:
            heapq.heappush(maxheap, -num)
        
        # swap `num` into heap
        # making sure heap stays size `k`
        elif num > maxheap[0]: 
            heapq.heappop(maxheap)
            heapq.heappush(maxheap, -num)


    def getKthSmallest(self):
        return -self.maxheap[0] # negative since maxheap

Add Function Time Complexity $O(\log k)$ for every number added. This is because the heap contains at most k numbers, which means it has a height of O(log k). So adding to it is $O(\log k)$.

Find Kth Smallest Element Time Complexity $O(1)$. The kth smallest element is always at the root node of the heap.

Space Complexity $O(k)$ to store the heap.

Note on Sorted Array solution: