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.