Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

3 votes
Accepted

Find the smallest difference between two numbers in a DS in O(1) time

Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the ...
user avatar
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations. A possible data structure consists of an AVL tree $T$ plus a priority ...
user avatar
  • 22.8k
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes: the minimum difference between two leaves in the subtree; the minimum and maximum values of a leaf in ...
user avatar
  • 7,154

Top 50 recent answers are included