searching a 2D array (nxn) with comlexity of O(n)

M

MIA

Hi,
I have an nxn array in which in each row is consisting of +ve and -ve
numbers, such that -ve number comes before +ve numbers. e.g.

-45 | -9 | -3 | 2
===================
-5 | -9 | 21 | 12
===================
-4 | 19 | 18 | 5
===================
-15 | -17 | 38 | 3

all I have to do is to find the row with max number of +ve integers.
in the above case 3rd row.

My problem is that I have to make algorithm linear i.e. O(n) instead
of O(n^2).
any sugestions.
 
A

Attila Feher

MIA said:
Hi,
I have an nxn array in which in each row is consisting of +ve and -ve
numbers, such that -ve number comes before +ve numbers. e.g.

-45 | -9 | -3 | 2
===================
-5 | -9 | 21 | 12
===================
-4 | 19 | 18 | 5
===================
-15 | -17 | 38 | 3

all I have to do is to find the row with max number of +ve integers.
in the above case 3rd row.

My problem is that I have to make algorithm linear i.e. O(n) instead
of O(n^2). any sugestions.

Is this a homework assigment? I just guess from this:

Organization: York University
Description: Founded in 1959, York University is the third largest
university in Canada with more than 40,000 full-time and
part-time students. A 600-acre campus in the northwest
area of Metropolitan Toronto is the home for York's
Faculties of Administrative Studies, Arts, Education,
Environmental Studies, Fine Arts, Science, Graduate
Studies, and Osgoode Hall Law School. York's Glendon
College is a bilingual liberal arts college located on its
own 85-acre parkland campus near the centre of the city.
 
J

Jerry Coffin

Hi,
I have an nxn array in which in each row is consisting of +ve and -ve
numbers, such that -ve number comes before +ve numbers. e.g.

-45 | -9 | -3 | 2
===================
-5 | -9 | 21 | 12
===================
-4 | 19 | 18 | 5
===================
-15 | -17 | 38 | 3

all I have to do is to find the row with max number of +ve integers.
in the above case 3rd row.

My problem is that I have to make algorithm linear i.e. O(n) instead
of O(n^2).
any sugestions.

I suspect you'll get more help in a newsgroup devoted to algorithms than
one devoted to a language.

My immediate guess is that it's not possible to make it linear on N.
Making it O(N lg N) is fairly straightforward, but unless there's more
organization to the numbers than you've said, making it O(N) shouldn't
be possible.

My reasoning is as follows: you've said nothing about a relationship
between rows, so you apparently need to search all the rows. That's
clearly O(N) by itself. For the overall algorithm to remain O(N), you'd
have to search each row in constant time. TTBOMK, that's just not
possible; O(Lg2 N) is the best that's known (i.e. a binary search for
the first positive number in the row).

If the numbers you posted are representative, there may be a possibility
though: in the numbers you gave, the position of the first +ve in any
given row differs from the one in the previous row by no more than one
position.

If that is always the case, then you can do an O(Lg2 N) search for the
first +ve in the first row, and then search through only three numbers
for each consecutive row to find it.

I have no idea whether that's always the case or not though -- it may be
purely an accident that the numbers you posted happen to follow this
particular pattern.
 
K

Kevin Saff

Jerry Coffin said:
(e-mail address removed) says> My reasoning is as follows: you've said nothing about a relationship
between rows, so you apparently need to search all the rows. That's
clearly O(N) by itself. For the overall algorithm to remain O(N), you'd
have to search each row in constant time. TTBOMK, that's just not
possible; O(Lg2 N) is the best that's known (i.e. a binary search for
the first positive number in the row).

I'm sorry, there is a very simple O(N) solution to this problem, but since
it looks like homework, I'm not sure I want to post it. A hint: we do have
to search all the rows, but we can be smart about where we start searching.
 
T

Thomas Matthews

Jerry said:
I suspect you'll get more help in a newsgroup devoted to algorithms than
one devoted to a language.

My immediate guess is that it's not possible to make it linear on N.
Making it O(N lg N) is fairly straightforward, but unless there's more
organization to the numbers than you've said, making it O(N) shouldn't
be possible.

My reasoning is as follows: you've said nothing about a relationship
between rows, so you apparently need to search all the rows. That's
clearly O(N) by itself. For the overall algorithm to remain O(N), you'd
have to search each row in constant time. TTBOMK, that's just not
possible; O(Lg2 N) is the best that's known (i.e. a binary search for
the first positive number in the row).

If the numbers you posted are representative, there may be a possibility
though: in the numbers you gave, the position of the first +ve in any
given row differs from the one in the previous row by no more than one
position.

If that is always the case, then you can do an O(Lg2 N) search for the
first +ve in the first row, and then search through only three numbers
for each consecutive row to find it.

I have no idea whether that's always the case or not though -- it may be
purely an accident that the numbers you posted happen to follow this
particular pattern.

Just a note: for small values of N, a linear may be faster than a
binary search.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
 
N

Neil Gan

int Search(vector<vector<int> > vvMatrix)
{
assert(vvMatrix.size() != 0);

int nFstPositive=vvMatrix[0].size();
int nRet=0;

for (unsigned int i=0 ; i<vvMatrix.size() ; ++i)
{
while (nFstPositive > 0 && vvMatrix[nFstPositive-1] > 0)
{
--nFstPositive;
nRet=i;
}
}
return nRet;
}

Though it uses nested loops, it is still a linear algorithm, because
the total execution times of the inner loop is less than
vvMatrix[0].size()
 
J

Jerry Coffin

[ ... ]
Though it uses nested loops, it is still a linear algorithm, because
the total execution times of the inner loop is less than
vvMatrix[0].size()

I'm not sure I follow the reasoning here -- it still looks quadratic to
me.
 
M

MIA

Yes it is an assignment question for which I asked suggestions not
solution and I solved it already but I wanna know if someone has a
better solution.

many thanx to all of you who participate.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top