Count Negative Numbers in a Sorted Matrix

Binary SearchCountingMatrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, your task is to count the total number of negative numbers in the matrix. Return the total count.

Example 1

Input

[
  [
    4,
    3,
    2,
    -1
  ],
  [
    3,
    2,
    1,
    -1
  ],
  [
    1,
    1,
    -1,
    -2
  ],
  [
    -1,
    -1,
    -2,
    -3
  ]
]

Output

Explanation. There are 8 negative numbers in the matrix.

Example 2

Input

Output

Explanation. There are no negative numbers in the given matrix.

Example 3

Input

[
  [
    -1
  ]
]

Output

Explanation. The single element in the matrix is negative.

Follow-up: Can you implement a solution using a binary search for optimal performance on large matrices?

Constraints:

1. The number of rows, `m`, and columns, `n` are in the range `[1, 100]`.\n2. Each integer in `grid` ranges from `-100` to `100`.

Views: 3