Would this Greedy algorithm work??

[smithywill]

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.

[smithywill]

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

[nuzzle]

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.

[kilotaras]

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.