
May 26th, 2010, 05:02 PM
#1
Would this Greedy algorithm work??
Hey
Got an exam on Friday for algorithms, it isnt my strong suit to be honest. Anyways one past paper question asks to design a greedy algorithm:
Have two arrays, Array Left and Array Right.
Design an algorithm such that left(i)+right(j)=0
EG: Left= 3 7 2 2
Right=5 3 8 8
Answer=i=1 and j=2
Brute force results in worst case quadratic complexity and is an inefficent solution.
My Solution:
Put the two arrays together, eg: 2 7 2 2 5 3 8 8
Sort them, using mergesort or something. eg 8 8 3 2 2 3 5 7
Then have two pointers L and R.
L=1 //starts at begining of array
R=n // Starts at end of array
IF L+R < 0 //undershot target value 0
then
L=L+1
else IF L+R >0 //overshot target value 0
then
R=R1
IF L+R=0 // solution found
then
return true
IF L>R //pointers cross so no solution
then
return false
This seems ok to me, what do you think?? Would result in worst case O(n.log n) due to the merge sort.

May 27th, 2010, 06:09 AM
#2
Re: Would this Greedy algorithm work??
Anyone? Just a quick Yes or No would help me out.

May 27th, 2010, 05:09 PM
#3
Re: Would this Greedy algorithm work??
Originally Posted by smithywill
Anyone? Just a quick Yes or No would help me out.
I don't think you have a working algorithm.
Is the problem that you want to know if a number in one array is present with the opposite sign in the other array? That would make their sum zero, right.
I don't quite see what merging and sorting the arrays will buy you. By doing that you no longer know which original array each number belongs to. A pair of numbers that sums to zero can as well come from the same array.
I suggest you just enter all numbers of one array into a hash set. Then you walk through the other array and check whether you have a match with opposite sign in the set. It's an O(N) algorithm.
Last edited by nuzzle; May 28th, 2010 at 02:00 AM.

November 27th, 2010, 04:21 AM
#4
Re: Would this Greedy algorithm work??
No it wont work.
Consider
Left = 3 3
Right = 0 0
Merged and sorted = 3 0 0 3
L = 1
R = n
IF L+R=0 // solution found
then
return true
Though its obvious thats not true.
You should sort both left and right separately.
sort(left)
sort(right)
R = n;
L = 1;
if L + R < 0
L = L+1;
if L + R >0
R = R  1;
if L + R = 0
return true;
if(L>n or R<0)
return false.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
