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=R-1

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.

Anyone? Just a quick Yes or No would help me out.

Quote:

---

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.

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.