How can binary search be applied in the Count Negative Numbers in a Sorted Matrix problem?

You can apply binary search on each row to find the first negative number, leveraging the sorted nature of each row for faster identification.

What is the time complexity of the brute force solution for this problem?

The time complexity of the brute force approach is O(m * n), where m is the number of rows and n is the number of columns.

How does the sorted nature of the matrix help in optimizing the solution?

The sorted matrix allows you to use binary search, reducing the time complexity from O(m * n) to O(m * log(n)) by quickly locating negative numbers in each row.

What is the primary pattern in the Count Negative Numbers in a Sorted Matrix problem?

The primary pattern in this problem is applying binary search over the valid answer space, taking advantage of the matrix’s sorted structure.

Can the Count Negative Numbers in a Sorted Matrix problem be solved without binary search?

Yes, it can be solved using a brute force approach, though binary search is the more efficient method in terms of time complexity.

#1351

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid ，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。请你统计并返回 grid 中负数的数目。示例 1：输入： grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 输出： 8 解释： …

数组二分查找矩阵

题目描述

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。请你统计并返回 grid 中负数的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

提示：

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

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

lightbulb

解题思路

方法一：从左下角开始遍历

由于矩阵是按行和按列非严格递减排序的，我们可以从矩阵的左下角开始遍历，记当前位置为 $(i, j)$ 。

如果当前位置的元素大于等于 $0$ ，说明该行的前面所有元素也都大于等于 $0$ ，因此我们将列索引 $j$ 向右移动一位，即 $j = j + 1$ 。

如果当前位置的元素小于 $0$ ，说明该列的当前元素以及其右侧的所有元素都是负数，因此我们可以将负数的数量增加 $n - j$ （其中 $n$ 是矩阵的列数），然后将行索引 $i$ 向上移动一位，即 $i = i - 1$ 。

我们重复上述过程，直到行索引 $i$ 小于 $0$ 或列索引 $j$ 大于等于 $n$ 。最终，负数的数量即为答案。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate may demonstrate an understanding of binary search optimization.
question_mark
Look for efficient handling of the matrix’s sorted properties.
question_mark
Candidates should be able to quickly decide between brute force and optimized approaches.

warning

常见陷阱

外企场景

error
Failing to recognize that binary search can be used due to the sorted matrix.
error
Inadequate handling of early exits when searching through rows.
error
Over-complicating the solution by not leveraging matrix properties effectively.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be varied by changing the matrix dimensions or having different constraints on the range of values.
arrow_right_alt
You can modify the matrix to be sorted in a different order (non-increasing vs non-decreasing) and require adaptation of the approach.
arrow_right_alt
The problem can be extended to handle larger matrices with additional memory and performance considerations.

help

常见问题

外企场景

继续练习

#1337 矩阵中战斗力最弱的 K 行 #1292 元素和小于等于阈值的正方形的最大边长 #1439 有序矩阵中的第 k 个最小数组和