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:

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:

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:

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

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

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: