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 sorted

For example :

-3	-2	-1	1
-2	-12	3	4
4	5	7	8

 

Naive Solution :

1. Traverse the matrix from left -> right, top -> bottom order
2. Count the number of negative elements
3. Hence, O(n^2) complexity

 

Optimal Solution :

1. Traverse the matrix from right-> left, top -> bottom.
2. Find the last negative number’s index in the 1st row.
3. Using this information, find the last negative number’s index in the 2nd row.
4. 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]