educative.io

Why not two binary search trees?

Courses
,
#1

Hey all!

I was thinking through this problem. The solution I would have come up with would have been similar, but to use two balanced binary search trees instead of heaps (similar to a Java SortedSet or something). This seems to give an overall runtime of O(n log k) which might be slightly improved over the two heaps solution.

At each step, we effectively do the same thing, expect for the max and min now take O(log k) and the linear search for the node to be removed is swapped for the tree lookup at O(log k).

I was wondering if anyone had any thoughts about solving this problem in this way.

3 Likes
#2

Hi @Leland_Miller,

Yeah, it makes sense. However, as you can see that the name of the chapter is Pattern: Two Heaps, so we are bound to use heaps in the solution.

#3

I guess the current example could use Binary Search Tree, the Time Complexity of finding the biggest or smallest value in the Binary Search Tree is O(log(n)), whilst using Heap is O(1) in the last example.

#4

Thanks for pointing this out, I’d think it would be the superior solution for an interview as it’s substantially faster.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Sliding Window Median (hard) - Grokking the Coding Interview: Patterns for Coding Questions