[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 sorted
For example :
| -3 | -2 | -1 | 1 |
| -2 | -12 | 3 | 4 |
| 4 | 5 | 7 | 8 |
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 !
[/et_pb_text][/et_pb_column][/et_pb_row][/et_pb_section]
