Algorithm :
Naive Algorithm Will O(N^4) Use Four Loop & keep Checking for all four elements.its so Naive ,easily understood-able..
Algorithm:
Little Efficient O(N^3).
Sort the input array. O(nlogn)
Then take 4 pointers p1,p2,p3,p4 where
0<=p1<=n-3 1st loop
p1+1<=p2<=n-2 1st inner loop
in loop set p3=p1+ & p4=n-1
( e.g. Take 3 Pointer Pointing to three successive indexes from starting & 4th Pointer pointing to n-1th position. )
Now use same algo we used to check for two elements in sorted array whose sum equals to given element or not 3rd Inner Loop
Most Efficient O(N^2)
Algorithm:
Create an array of all possible PAIR sums..that would be done in O(n^2)
Sort the Above array of size n^2 that can be done in.O(n^2log(n)) .
Then Search this array for two pairs..that sum to the required value..this can be done by maintaining two pointer One at the starting index..and other at the highest index..and moving them accordingly..(if sum of pair exceeds given value..move up highest value pointer..else move down..lowest value pointer) .it Will take O(n)
Total Time Complexity Will be O(n^2logn) +O(nlogn) +O(n)=O(n^2logn).
Space Complexity O(N^2).
Naive Algorithm Will O(N^4) Use Four Loop & keep Checking for all four elements.its so Naive ,easily understood-able..
Algorithm:
Little Efficient O(N^3).
Sort the input array. O(nlogn)
Then take 4 pointers p1,p2,p3,p4 where
0<=p1<=n-3 1st loop
p1+1<=p2<=n-2 1st inner loop
in loop set p3=p1+ & p4=n-1
( e.g. Take 3 Pointer Pointing to three successive indexes from starting & 4th Pointer pointing to n-1th position. )
Now use same algo we used to check for two elements in sorted array whose sum equals to given element or not 3rd Inner Loop
Most Efficient O(N^2)
Algorithm:
Create an array of all possible PAIR sums..that would be done in O(n^2)
Sort the Above array of size n^2 that can be done in.O(n^2log(n)) .
Then Search this array for two pairs..that sum to the required value..this can be done by maintaining two pointer One at the starting index..and other at the highest index..and moving them accordingly..(if sum of pair exceeds given value..move up highest value pointer..else move down..lowest value pointer) .it Will take O(n)
Total Time Complexity Will be O(n^2logn) +O(nlogn) +O(n)=O(n^2logn).
Space Complexity O(N^2).
4 comments :
I don't understand your O(n^3) first of all..
i don't understand the 3rd and 4th pointer thing..
could u explain it with example??
The third method is cool!
But, I wasn't able to understand the second method that takes O(n^3) time.
Can you explain it a bit clearly?
Well, I seem to have a doubt in the third method.
Supposing there are 4 numbers,then the possible pair sums would be
1-1,1-2,1-3,1-4,2-2,2-3,2-4,3-3,3-4,4-4.
Now after sorting the pair sums, if we get two numbers that equal the given sum such that those two numbers are pair sums of 1-2,2-3. Now though we get the given sum, we are using only 3 numbers(1,2,3) and not 4 as required.
Am I correct?
Hey Karthik
I believe according to the 3rd method, you need to sort the pair sums, as in your example
2 3 4 5 4 5 6 6 7 8
Ideally, the pairsum should be an object type and it should contain the elements which resulted in this sum as attributes
Hence while checking from first pointer and last pointer, we can easily identify the numbers
Post a Comment