veerf1
BAN USER1.Sort the n numbers O(nlogn)
2.Scan the sorted array and fix 2 pointers first and last such that first+last < reqd_sum : O(n)
3.Now search for the third element
Step3 depends on both step1 and step2
Complexity= O(nlogn*n)+O(n)=O(n^2 logn)
Its similar to the prob of finding 2 numbers in a sorted array in O(nlogn)+O(n) except that we need to have sorted array in which we know two elements and we search for 3 rd element
Algorithm:
1. Convert the BST into a circular doubly linked list.
2. The list's head(say h) has its left pointer pointing to the last node. Remember the left pointer in a node temp.
3. Break the circle by changing left pointer for first node and right ptr of tail node
temp=h->left;(currently last node)
h->left=NULL;
temp->right=NULL;
Note that it is easier to convert into a circular doubly list(head's left always points to last node) and then break the circle rather than having to maintain head and tail pointer(especially while forming the list).
4. Now maintain 2 pointers start and end pointing to first and last node of the doubly linked list.
5.while(start->value<end->value)
{
if(start->val+end->val==sum)
{
print the two node values
start=start->right;
end=end->left
}
else if(start->val+end->val>sum)
end=end->left;
else
start=start->right;
}
Complexity: Transforming BST to DLL = O(N)
Finding the pair that sum up=O(N). Just one scan of the entire list
Total Complexity= O(N)
Algorithm:
1. Convert the BST into a circular doubly linked list.
2. The list's head(say h) has its left pointer pointing to the last node. Remember the left pointer in a node temp.
3. Break the circle by changing left pointer for first node and right ptr of tail node
temp=h->left;(currently last node)
h->left=NULL;
temp->right=NULL;
Note that it is easier to convert into a circular doubly list(head's left always points to last node) and then break the circle rather than having to maintain head and tail pointer(especially while forming the list).
4. Now maintain 2 pointers start and end pointing to first and last node of the doubly linked list.
5.while(start->value<end->value)
{
if(start->val+end->val==sum)
{
print the two node values
start=start->right;
end=end->left
}
else if(start->val+end->val>sum)
end=end->left;
else
start=start->right;
}
RepKinsleyJames, Network Engineer at Accenture
I graduated from College with a master’s degree in arthrogryposis. After graduation I am working as a manager in ...
It woud work only for positive numbers. Array indexes cant be stored as negative
- veerf1 September 11, 2011