Count Negative Numbers in a Row And Column Wise Sorted Matrix [Amazon]
[et_pb_section admin_label="section"][et_pb_row admin_label="row"][et_pb_column type="4_4"][et_pb_text admin_label="Text" background_layout="light" text_orientation="left" text_text_color="#000000" use_border_color="off" border_color="#ffffff" border_style="solid"] 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 sortedFor example :
| -3 | -2 | -1 | 1 |
| -2 | -12 | 3 | 4 |
| 4 | 5 | 7 | 8 |
- Traverse the matrix from left -> right, top -> bottom order
- Count the number of negative elements
- Hence, O(n^2) complexity
- 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 ![/et_pb_text][/et_pb_column][/et_pb_row][/et_pb_section]