here's a coding interview question from
Amazon it is find the number of negative
integers in a row wise and column wise
sorted matrix so here's an example as
you can see the numbers in the matrix
are sorted row wise and column wise and
here we have four negative numbers so
our function let's say func
should return four in this case here's a
naive solution for this problem we'll
just start from the first row and we'll
count the number of negative numbers one
by one so we find three negative numbers
here and in the second row we find it
just one negative number and in the
third row in the last row we find zero
negative numbers so we add them up and
we get four in this case the worst case
scenario for this solution is when we
have all negative numbers in the matrix
and in that case we'll need to traverse
all the elements in the array or matrix
so the time complexity for this solution
would be Big O of n times M where n is
the number of rows we have and M is
number of columns we have in the matrix
here is the optimal solution for this
problem we'll start from the top right
corner and we'll find the position of
the last negative number in the first
row and using that information we'll
find the position of the last negative
number in the second row this one and so
on until we get to the last row or we
don't have any more negative numbers to
count for the first row the position of
the last negative number is negative one
is two so we'll know that the number of
negative numbers in this row is just
three and same thing with the second row
the position of the last negative number
is zero so the number of negative
numbers is just one here and we have
zero negative numbers in the last row
we'll add them up and we get the answer
for the time complexity for this
solution is an order of
Plus em we're again n is the number of
rows and M is a number of columns we
have so here's the optimal solution in
code we're defining our function here
with the matrix and the number of rows
and the number of columns as input we
initialize and count to zero which we're
going to use to keep track of the number
of negative numbers we've seen so far
and I to zero which is our row index and
j2m minus one which is our column index
so we'll use I and J to keep track of
which element we are looking at so while
J is larger than or equal to zero so we
still have more negative numbers to
count and I is less than n so we haven't
got to that last row yet if the element
we're looking at M I J is an earlier
number then we found the last negative
number in the row so we increment the
count with J plus 1 and then we go to
the next row if the number we were
looking at is not a negative number then
we'll move our pointer to the left or
we'll try the same thing with the number
on the left and we'll repeat this
process over and over again until we get
the total number of negative numbers in
this matrix and then we're going to
return that alright thanks for watching
this video if you're watching this on
YouTube make sure to check out the
original article on gigs for gigs in the
description below