Count Negative Numbers in a Sorted Matrix
Problem
Given an m x n matrix grid whose rows and columns are both sorted in non-increasing order, return the count of negative numbers in grid.
grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]8def count_negatives(grid):
m, n = len(grid), len(grid[0])
r, c, ans = m - 1, 0, 0
while r >= 0 and c < n:
if grid[r][c] < 0:
ans += n - c
r -= 1
else:
c += 1
return ansfunction countNegatives(grid) {
const m = grid.length, n = grid[0].length;
let r = m - 1, c = 0, ans = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) { ans += n - c; r--; } else c++;
}
return ans;
}class Solution {
public int countNegatives(int[][] grid) {
int m = grid.length, n = grid[0].length;
int r = m - 1, c = 0, ans = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) { ans += n - c; r--; } else c++;
}
return ans;
}
}int countNegatives(vector>& grid) {
int m = grid.size(), n = grid[0].size();
int r = m - 1, c = 0, ans = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) { ans += n - c; r--; } else c++;
}
return ans;
} Explanation
The matrix is sorted so each row and each column decreases left-to-right and top-to-bottom. Instead of scanning every cell, we walk a staircase from the bottom-left corner and count negatives in one sweep.
We start at row r = m - 1, column c = 0. From this corner each step is an easy decision: if the current cell is negative, every cell to its right is also negative.
When grid[r][c] < 0, we add n - c (this cell plus everything to its right in the row) to ans and move up with r -= 1. When grid[r][c] >= 0, this cell isn't negative, so we move right with c += 1 to look for the boundary.
Each step either drops a row or advances a column, so we never revisit anything and finish in O(m + n) time.
Example: in [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] the staircase walk tallies 8 negative cells.