1351.count-negative-numbers-in-a-sorted-matrix.md

1351. Count Negative Numbers in a Sorted Matrix

Brute Force

We can count the negative numbers in the matrix by iterating each element.

def countNegatives(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] < 0:
                count += 1
    return count

• Time Complexity: O(m * n).
• Space Complexity: O(1).

Binary Search in Each Row (Column) (AC)

For each row (column), we can use binary search to find the first negative number, and the count of negative numbers will be n - index. This is AC but not optimal because we don't use the sorted property of between rows (columns).

fun countNegatives(grid: Array<IntArray>): Int {
    var count = 0
    for (i in 0 until grid.size) {
        val index = binarySearch(grid[i])
        count += grid[i].size - index
    }
    return count
}

private fun binarySearch(array: IntArray): Int {
    var left = 0
    var right = array.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (0 <= array[middle]) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return left
}

• Time Complexity: O(m * lg(n)).
• Space Complexity: O(1).

Count in Z-Shape (AC)

Since each row (column) is sorted, we can count the negative numbers in a Z-shape.

We can count the number of negative numbers by starting at the bottom-left corner:

• If grid[i][j] > 0: all elements in that row above it (including itself) are > 0, so we can move to the next column and count i + 1 elements.
• Else: move up a row (i--), because elements below are larger than mid.

// The initial position of r and c, and its direction
   + + + +
↑  + + - - 
r  - - - - 
   c → 

// The position of r when breaking the while loop
            r
  +   r +     -
  +     -     -
r +     -     -

We start from left-botton corner, and move up to right-top corner, and count the negative numbers in each column.

fun countNegatives(grid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    var r = m - 1
    var c = 0
    var count = 0
    for (c in 0 until n) {
        while (r >= 0 && grid[r][c] < 0) {
            r--
        }
        count += m - r - 1
    }
    return count
}

def countNegatives(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])

    r = m - 1
    c = 0
    count = 0
    # Please note that we don't check if r < 0, becase r will become -1 but we still 
    # need to count the following columns. 
    # See the example below (all numbers are negative):
    # -1, -1, -1
    # -1, -1, -1
    while c < n:
        while 0 <= r and grid[r][c] < 0:
            r -= 1
        count += m - r - 1
        c += 1
        
    return count

# Equivalently, starting from right-top corner, and move down to left-bottom corner.
# + + + - - -
#        <- c 
# + + + - - -
#     c 
def countNegatives(self, grid: List[List[int]]) -> int:
    count = 0
    n = len(grid[0])
    c = n - 1

    for r in grid:
        while c >= 0 and r[c] < 0:
            c -= 1
        
        count += (n - c - 1)
    
    return count

• Time Complexity: O(m + n).
• Space Complexity: O(1).