Start from two ends of the sorted list and if their sum is less than M then move the first pointer towards right and check again. If their sum is greater than M then move the second pointer towards left.
This is when we were given a sorted list of numbers and we can find x,y (if exists) in O(n)...
Can we do something better if it is a Binary Search Tree... (I am not able to think of an algorithm with at least O(n) if BST is given
)You are right. I'm just modifying your approach little bit. The concept will be the same.
Take one pointer pointing to minimum of BST. (O(lg n))
Take one pointer pointing to maximum of BST. (O(lg n))
Now do the same thing.
If the sum is greater than SUM then go to predecessor of maximum node.
Else if sum is less than SUM then go to successor of minimum node.
T.C. is O(n) -->( A Tight Upper Bound )
Take one pointer pointing to minimum of BST. (O(lg n))
Take one pointer pointing to maximum of BST. (O(lg n))
Now do the same thing.
If the sum is greater than SUM then go to predecessor of maximum node.
Else if sum is less than SUM then go to successor of minimum node.
T.C. is O(n) -->( A Tight Upper Bound )
you are correct on saying that finding a predecessor or successor takes O(lgn) time, but that is only for that particular node. but suppose starting from a particular node you go to say n successors successively, you will be taking not more than O(n) time.
why?
say we consider a node in a tree, how many times are you going to access this node when finding successors?
not more than 3 times. why?
1) to go to the left subtree
2) to move from left subtree to right
3) to move out of the subtree rooted at this node.
3rd case occurs when any parent is a successor. once this subtree is accessed you are never going to come back to it again during the whole traversal.
its bit difficult to explain like this but i hope little thinking on your side will satisfy you.
hope this example may clear out some more of it...
in a sorted array finding the successor you visit any index just once. why? because when you move beyond it there is no coming back. eg 3 5 6 7 8 9
once you reach 7, you will be never coming back to smaller nos.
why?
say we consider a node in a tree, how many times are you going to access this node when finding successors?
not more than 3 times. why?
1) to go to the left subtree
2) to move from left subtree to right
3) to move out of the subtree rooted at this node.
3rd case occurs when any parent is a successor. once this subtree is accessed you are never going to come back to it again during the whole traversal.
its bit difficult to explain like this but i hope little thinking on your side will satisfy you.
hope this example may clear out some more of it...
in a sorted array finding the successor you visit any index just once. why? because when you move beyond it there is no coming back. eg 3 5 6 7 8 9
once you reach 7, you will be never coming back to smaller nos.
No comments:
Post a Comment