Count Negative Numbers in a Row And Column Wise Sorted Matrix [Amazon]
The given Matrix satisfies the following properties :
M [ i ] [ j ] ≤ M [ i ] [ j + 1 ] // Column wise sorted
M [ i ] [ j ] ≤ M [ i + 1 ] [ j ] // Row wise sorted
For example :
Naive Solution :
- Traverse the matrix from left -> right, top -> bottom order
- Count the number of negative elements
- Hence, O(n^2) complexity
Optimal Solution :
- Traverse the matrix from right-> left, top -> bottom.
- Find the last negative number’s index in the 1st row.
- Using this information, find the last negative number’s index in the 2nd row.
- Keep repeating this process until either you run out of negative numbers or you get to the last row.
Watch the following video to see this algorithm in action !
Let us know if you would like to know more about matrix problems, by leaving your comments !