#1351

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix requires counting negative numbers in a matrix sorted in non-increasing order using binary search or brute force.

array binary search matrix

Problem Statement

You are given a matrix grid with dimensions m x n where each row and column is sorted in non-increasing order. Your task is to count the number of negative numbers in this matrix.

For example, consider the matrix [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]. The matrix contains 8 negative numbers, so the expected output is 8.

Examples

Example 1

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Output: 8

There are 8 negatives number in the matrix.

Example 2

Input: grid = [[3,2],[1,0]]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Binary Search Optimization

Since each row is sorted, you can apply binary search to find the first negative number in each row. This reduces the time complexity compared to brute force and allows you to efficiently count negative numbers in the matrix.

Brute Force Approach

If you're looking for a simpler solution, a brute force approach can iterate over every element in the matrix and check if it’s negative. This method is slower but easy to implement and understand.

Row-based Scanning with Early Exit

You can iterate through the rows and use the sorted nature of the rows to exit early when you encounter non-negative numbers. This reduces unnecessary checks and improves performance in some cases.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the binary search approach is O(m * log(n)), where m is the number of rows and n is the number of columns. The brute force approach has a time complexity of O(m * n). Space complexity for both approaches is O(1), as no additional data structures are required.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Traverse from the Bottom-Left Corner

Since the matrix is sorted in non-strictly decreasing order both row-wise and column-wise, we can start traversing from the bottom-left corner of the matrix. Let the current position be $(i, j)$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#1337 the k weakest rows in a matrix #1292 maximum side length of a square with sum less than or equal to threshold #1439 find the kth smallest sum of a matrix with sorted rows