Count Negative Numbers in a Sorted Matrix — DSA

Problem#

Given an m x n matrix sorted in non-increasing order both per-row and per-column, return the count of negative numbers.

Examples#

[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] → 8
[[3,2],[1,0]] → 0

Constraints#

m == grid.length, n == grid[i].length, 1 <= m, n <= 100.

Approach#

Start at the bottom-left. If the current cell is negative, all cells to its right in this row are negative too (each row is sorted descending): add n - col and move up. Otherwise, move right.

Solution#

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int r = m - 1, c = 0, count = 0;
        while (r >= 0 && c < n) {
            if (grid[r][c] < 0) {
                count += n - c;
                --r;
            } else {
                ++c;
            }
        }
        return count;
    }
};

func countNegatives(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    r, c, count := m-1, 0, 0
    for r >= 0 && c < n {
        if grid[r][c] < 0 {
            count += n - c
            r--
        } else {
            c++
        }
    }
    return count
}

from typing import List

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c, count = m - 1, 0, 0
        while r >= 0 and c < n:
            if grid[r][c] < 0:
                count += n - c
                r -= 1
            else:
                c += 1
        return count

function countNegatives(grid) {
    const m = grid.length, n = grid[0].length;
    let r = m - 1, c = 0, count = 0;
    while (r >= 0 && c < n) {
        if (grid[r][c] < 0) {
            count += n - c;
            r--;
        } else {
            c++;
        }
    }
    return count;
}

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int r = m - 1, c = 0, count = 0;
        while (r >= 0 && c < n) {
            if (grid[r][c] < 0) {
                count += n - c;
                r--;
            } else {
                c++;
            }
        }
        return count;
    }
}

function countNegatives(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    let r = m - 1, c = 0, count = 0;
    while (r >= 0 && c < n) {
        if (grid[r][c] < 0) {
            count += n - c;
            r--;
        } else {
            c++;
        }
    }
    return count;
}

Editorial#

The bottom-left corner is the smallest cell in its row and the largest in its column — a perfect pivot to advance one step at a time. Each step removes a full row or column, so the total work is O(m + n).

Complexity#

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

Concept revision#

Kth Smallest Element in a Sorted Matrix

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#