Is Count Negative Numbers in a Sorted Matrix easy or hard?

The problem is classified as Easy on LeetCode with a high acceptance rate around 79%. The brute force approach is trivial, while the binary search solution demonstrates better algorithmic thinking using sorted properties.

Count Negative Numbers in a Sorted Matrix Python/Java solution

Most solutions iterate through rows and apply binary search to find the first negative index. The logic is identical across languages like Python, Java, C++, and JavaScript, with only syntax differences for the binary search implementation.

How to solve Count Negative Numbers in a Sorted Matrix in O(m log n)?

Iterate through each row of the matrix and perform binary search to find the first negative value. Because the row is sorted in non-increasing order, all elements after that index are negative. Add the count of those elements to the total and repeat for all rows.

What is the best approach for Count Negative Numbers in a Sorted Matrix?

Binary search on each row is the most common optimal solution. Because every row is sorted in non-increasing order, you can locate the first negative value using binary search and count the remaining elements. This results in O(m log n) time and O(1) space.

Is Count Negative Numbers in a Sorted Matrix asked at Google/Amazon/Meta?

Matrix traversal and binary search problems like this frequently appear in interviews at large tech companies including Amazon and Google. The problem tests your ability to recognize sorted structure and reduce unnecessary work using binary search.

What data structure is used in Count Negative Numbers in a Sorted Matrix?

The core data structure is a 2D array (matrix). The optimized solution combines matrix traversal with binary search on each row to efficiently locate the boundary where negative numbers begin.

What is the time complexity of Count Negative Numbers in a Sorted Matrix?

The brute force solution scans every element and runs in O(m * n) time. The optimized approach applies binary search on each row, reducing the complexity to O(m log n) while keeping space usage at O(1).

Description Hints 1 Solution Video 11:10

1351. Count Negative Numbers in a Sorted Matrix

Easy79.6% acceptance6 companies

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

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

Constraints:

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

Follow up: Could you find an O(n + m) solution?

Asked at 6 companies

Arista Networks Amazon

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Use binary search for optimization or simply brute force.

11:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution