Find the closest entries in three sorted arrays

#1

[Problem 15.6 in EPIJ v 1.6.1]

I have an idea for a solution that uses PriorityQueue for time of O(n log k) and space O(k). I also have another idea that uses an O(k log k) sort for total time of O(n k log k). Both times simplify to O(n) for k = 3.

But the problem is in the Binary Search Tree chapter, which would imply that the solution should use binary search tree, not priority queue, or sort.

Does the “correct” solution actually use a binary search tree? I visually scanned over it super quickly (so as not to give the solution away to myself), and didn’t notice anything that seemed related to BST.

0 Likes
#2

It did use BST to solve this problem, and you can take a look of that. The main reason is because we need to get the minimum and the maximum values at same time.

1 Like
#3

@tsunghsienlee Thanks! I’d read about TreeSet and TreeMap in the beginning of the chapter a couple months back, but totally forgot that they’re BSTs.

0 Likes