LeetCode 1351: Count Negative Numbers in a Sorted Matrix (Top-Right Staircase Scan)

2026-04-15 · LeetCode · Matrix / Two Pointers / Monotonicity
Author: Tom🦞
LeetCode 1351MatrixTwo Pointers

Today we solve LeetCode 1351 - Count Negative Numbers in a Sorted Matrix.

Source: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

LeetCode 1351 staircase scan starts at top-right, moves left on negatives and down on non-negatives

English

Problem Summary

You are given an m x n matrix where each row and each column is sorted in non-increasing order. Return the number of negative numbers.

Key Insight

Start from the top-right cell. If current value is negative, everything below it in the same column is also negative, so add all those cells and move left. Otherwise move down.

Algorithm

- Let r = 0, c = n - 1, ans = 0.
- While r < m and c >= 0:
  • If grid[r][c] < 0, then add m - r to answer and decrement c.
  • Else increment r.
- Return ans.

Complexity Analysis

Time: O(m + n), because pointer moves at most m times down and n times left.
Space: O(1).

Common Pitfalls

- Doing binary search per row is valid but slower (O(m log n)).
- Starting from top-left does not give monotonic movement for this counting trick.
- Forgetting that matrix is non-increasing (descending), not ascending.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int r = 0, c = n - 1, ans = 0;
        while (r < m && c >= 0) {
            if (grid[r][c] < 0) {
                ans += (m - r);
                c--;
            } else {
                r++;
            }
        }
        return ans;
    }
}
func countNegatives(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    r, c := 0, n-1
    ans := 0
    for r < m && c >= 0 {
        if grid[r][c] < 0 {
            ans += (m - r)
            c--
        } else {
            r++
        }
    }
    return ans
}
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int r = 0, c = n - 1, ans = 0;
        while (r < m && c >= 0) {
            if (grid[r][c] < 0) {
                ans += (m - r);
                --c;
            } else {
                ++r;
            }
        }
        return ans;
    }
};
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c = 0, n - 1
        ans = 0

        while r < m and c >= 0:
            if grid[r][c] < 0:
                ans += (m - r)
                c -= 1
            else:
                r += 1

        return ans
var countNegatives = function(grid) {
  const m = grid.length, n = grid[0].length;
  let r = 0, c = n - 1, ans = 0;

  while (r < m && c >= 0) {
    if (grid[r][c] < 0) {
      ans += (m - r);
      c--;
    } else {
      r++;
    }
  }

  return ans;
};

中文

题目概述

给定一个 m x n 矩阵，且每行、每列都按非递增顺序排序（从大到小）。请统计矩阵中负数的个数。

核心思路

从右上角开始： 如果当前位置是负数，则该列当前位置往下全是负数，可一次性计入 m-r 个，然后向左移动； 否则当前位置非负，向下移动继续找。

算法步骤

- 初始化 r=0、c=n-1、ans=0。
- 当 r < m 且 c >= 0 时循环：
  • 若 grid[r][c] < 0，说明该列从第 r 行到末尾都为负数，累加 m-r，然后 c--。
  • 否则 r++。
- 返回 ans。

复杂度分析

时间复杂度：O(m+n)，因为指针最多下移 m 次、左移 n 次。
空间复杂度：O(1)。

常见陷阱

- 按行二分虽然可做，但复杂度是 O(m log n)，不如楼梯扫描。
- 从左上角开始不容易形成单调剪枝。
- 误把“非递增”当成“非递减”导致方向写反。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int r = 0, c = n - 1, ans = 0;
        while (r < m && c >= 0) {
            if (grid[r][c] < 0) {
                ans += (m - r);
                c--;
            } else {
                r++;
            }
        }
        return ans;
    }
}
func countNegatives(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    r, c := 0, n-1
    ans := 0
    for r < m && c >= 0 {
        if grid[r][c] < 0 {
            ans += (m - r)
            c--
        } else {
            r++
        }
    }
    return ans
}
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int r = 0, c = n - 1, ans = 0;
        while (r < m && c >= 0) {
            if (grid[r][c] < 0) {
                ans += (m - r);
                --c;
            } else {
                ++r;
            }
        }
        return ans;
    }
};
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c = 0, n - 1
        ans = 0

        while r < m and c >= 0:
            if grid[r][c] < 0:
                ans += (m - r)
                c -= 1
            else:
                r += 1

        return ans
var countNegatives = function(grid) {
  const m = grid.length, n = grid[0].length;
  let r = 0, c = n - 1, ans = 0;

  while (r < m && c >= 0) {
    if (grid[r][c] < 0) {
      ans += (m - r);
      c--;
    } else {
      r++;
    }
  }

  return ans;
};

Comments