Searching a 2D Sorted Matrix (2) – JavaScript

Question

2D Matrix(m * n) of positive and negative numbers is given. Matrix is sorted rowwise and columnwise. You have to return the count of -ve numbers in most optimal way.

Origin from: CareerCup


Solution

// Time complexity: O(n+m)
function countNegativeElement(arr) {
    var m = arr.length,
        n = arr[0].length,
        row = 0,
        col = n - 1,
        count = 0;

    while (row <= (n - 1) && col >= 0) {
        if (arr[row][col] < 0) {
            count = count + col + 1;
            row++;
        } else {
            col--;
        }
    }
    console.log(count);
    return;
}

var arr = [
    [-100, -90, -80, -70, -60],
    [-50, -40, -30, -20, -10],
    [-9, -8, -7, -6, -5],
    [-4, -3, -2, -1, 0],
    [1, 2, 3, 4, 5]
];

countNegativeElement(arr);

Demo

Yang Zhao

Read more posts by this author.


Comment