[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]