Count Negative Numbers in a Column-Wise and Row-Wise Sorted Matrix - GeeksforGeeks

Count Negative Numbers in a Column-Wise and Row-Wise Sorted Matrix - GeeksforGeeks
Find the number of negative numbers in a column-wise / row-wise sorted matrix M[][]. Suppose M has n rows and m columns.

1. We start from the top right corner and find the position of the last negative number in the first row.
2. Using this information, we find the position of the last negative number in the second row.
3. We keep repeating this process until we either run out of negative numbers or we get to the last row.

O(n + m)

With the given example:
[-3, -2, -1,  1]
[-2,  2,  3,  4]
[4,   5,  7,  8]

Here's the idea:
[-3, -2,  ↓,  ←] -> Found 3 negative numbers in this row
[ ↓,  ←,  ←,  4] -> Found 1 negative number in this row
[ ←,  5,  7,  8] -> No negative numbers in this row 

def countNegative(M, n, m):

 

    count = 0 # initialize result

 

    # Start with top right corner

    i = 0

    j = m - 1 

 

    # Follow the path shown using arrows above

    while j >= 0 and i < n:

 

        if M[i][j] < 0:

 

            # j is the index of the last negative number

            # in this row.  So there must be ( j+1 )

            count += (j + 1)

 

            # negative numbers in this row.

            i += 1

 

        else:

            # move to the left and see if we can

            # find a negative number there

             j -= 1

    return count

O(M*n)

def countNegative(M, n, m):

    count = 0

 

    # Follow the path shown using arrows above

    for i in range(n):

        for j in range(m):

 

            if M[i][j] < 0:

                count += 1

 

            else:

                # no more negative numbers in this row

                break

    return count

Read full article from Count Negative Numbers in a Column-Wise and Row-Wise Sorted Matrix - GeeksforGeeks