## Friday, March 18, 2016

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