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

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.

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

MIA wrote:[color=blue]
> 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.[/color]

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.

--
Attila aka WW

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

In article <5f5518d0.0310030628.538897a3@posting.google.com >,
sfrazq@hotmail.com says...[color=blue]
> 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.[/color]

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

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

Jerry Coffin wrote:[color=blue]
> In article <5f5518d0.0310030628.538897a3@posting.google.com >,
> sfrazq@hotmail.com says...
>[color=green]
>>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.[/color]
>
>
> 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.
>[/color]

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

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

"Jerry Coffin" <jcoffin@taeus.com> wrote in message
news:MPG.19e73a398f582132989b46@news.clspco.adelph ia.net...[color=blue]
> In article <5f5518d0.0310030628.538897a3@posting.google.com >,
> sfrazq@hotmail.com says> My reasoning is as follows: you've said nothing[/color]
about a relationship[color=blue]
> 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).[/color]

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.

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

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[i][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()

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

In article <c47f6786.0310031259.7acfe04e@posting.google.com >,
neil_gan@hotmail.com says...

[ ... ]
[color=blue]
> 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()[/color]

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

--
Later,
Jerry.

The universe is a figment of its own imagination.

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

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.