CODEWITHSUNDEEP
arraysobjectdata-structures
Mark
Mark

Reputation: 8678

Implement data structure with efficient insert/findKthSmallest operations

I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be a good solution for this problem?

Upvotes: 1

Views: 51

Answers (2)

amrender singh
amrender singh

Reputation: 8239

You can use a Balenced Binary Search Tree(eg: red-black bst) for this.

  • Simply insert the nodes in the balenced bst. and each node maintains its rank within its own subtree. As we need to find the smallest element we can maintain count of elements in left subtree.

  • Now, start traversing from root and check:

    • if k = N +1, where N is number of nodes in roots left subtree. if yes than root is kth node.

    • else if K < N, continue to search in the left subtree of root.

    • else if k > N +1, then continue to search in the right subtree. And search for (K-N-1) smallest element.

Time complexity of insertion in a balenced bst is O(logn). While searching for kth smallest element will be O(h), where h is height of the tree.

Upvotes: 1

kaya3
kaya3

Reputation: 51037

You can use an order statistic tree. Essentially, it is a self-balancing binary search tree where each node also stores the cardinality of its subtree. Maintaining the cardinality does not increase the complexity of any tree operations, but allows your query to be performed in O(log n) time:

  • If the left subtree has cardinality > k, recurse on the left subtree.
  • Otherwise, if the left subtree has cardinality < k, recurse on the right subtree.
  • Otherwise the left subtree's cardinality equals k, so return the current node's element.

Upvotes: 0

Related Questions