Code Logo

Count Negative Numbers in a Sorted Matrix

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an m x n matrix where rows are sorted in non-increasing order (each row is descending) and columns are also sorted in non-increasing order (each column is descending), count the number of negative numbers in the matrix.

A brute force approach scans every element in O(m * n) time. Since rows are sorted descending, we can use binary search on each row to find the first negative number. All elements to the right of that position are also negative, so we add the count directly. This gives O(m * log n) time.

An even better O(m + n) approach starts from the top-right corner. If the current element is negative, all elements below it in the same column are also negative, so we add the remaining rows in that column and move left. If the current element is non-negative, move down. This avoids binary search entirely and runs in linear time.

Edge cases include a matrix with all positive numbers (return 0), all negative numbers (return m * n), a single row or column, and an empty matrix (return 0).

Binary search on each row finds the first negative index efficiently. Since each row is sorted descending, all elements from that index to the end are negative. The count is simply the row length minus the first negative index. Summing across all rows gives the total.

Example Input & Output

Example 1
Input
[[3,2],[1,0]]
Output
0
Explanation

All non-negative.

Example 2
Input
[[1,-1],[-1,-1]]
Output
3
Explanation

Three negatives in 2x2.

Example 3
Input
[[]]
Output
0
Explanation

Empty matrix.

Example 4
Input
[[-1]]
Output
1
Explanation

Single negative element.

Example 5
Input
[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output
8
Explanation

8 negatives in the 4x4 grid.

Algorithm Flow

Recommendation Algorithm Flow for Count Negative Numbers in a Sorted Matrix
Recommendation Algorithm Flow for Count Negative Numbers in a Sorted Matrix

Solution Approach

For each row, binary search to find the first negative index. Subtract from row length to get negatives in that row.

function solution(grid) {
  var count = 0;
  for (var r = 0; r < grid.length; r++) {
    var lo = 0, hi = grid[r].length;
    while (lo < hi) {
      var mid = Math.floor((lo + hi) / 2);
      if (grid[r][mid] >= 0) lo = mid + 1;
      else hi = mid;
    }
    count += grid[r].length - lo;
  }
  return count;
}

Time O(m log n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[][] grid) {
        int count = 0;
        for (int[] row : grid) {
            int lo = 0, hi = row.length;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (row[mid] >= 0) lo = mid + 1;
                else hi = mid;
            }
            count += row.length - lo;
        }
        return count;
    }
}