• 0

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.
 
const countNegative = ( M, n, m ) => {
var count = 0;
// start from top right
var i = 0;
var j = m - 1;
while ( j >= 0 && i < n ) {
if ( M[i][j] < 0 ) {
// last negative number is at index j. Hence, there j + 1 negative numebrs at index i
count += (j + 1);
// Move to the next row
i += 1;
} else {
// Move to the next column
j -= 1;
}
}
return count;
};
var M = [
[-3, -2, -1, 1],
[-2, -12, 3, 4],
[4, 5, 7, 8]
];
console.log(countNegative(M, 3, 4)); // 5
view raw countNegative.js hosted with ❤ by GitHub
 

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]