Any thoughts on follow-up?

  • 1

    I think we can keep both the kth smallest element and (k-1)th smallest element. If we insert or delete an element larger than the kth smallest element, the result remains unaffected. If something smaller than is inserted, compare it with the (k-1)th smallest element. The larger one becomes the new kth smallest element and adjust (k-1)th element accordingly.
    We may also need to keep track of the (k+1)th smallest element in case of deleting a node smaller than the kth element. However if we keep deleting nodes, we may need the (k+2, k+3, .... )th smallest element to stay correct.
    Any other ideas?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.