CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Would this Greedy algorithm work??

1. Junior Member
Join Date
May 2010
Posts
2

## 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

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.

2. Junior Member
Join Date
May 2010
Posts
2

## Re: Would this Greedy algorithm work??

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

3. Elite Member
Join Date
May 2009
Posts
2,413

## 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 01:00 AM.

4. Junior Member
Join Date
Nov 2010
Posts
1

## 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
•