Count Negative Numbers in a Sorted Matrix - Solution & Explanation
Problem Statement
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.lengthn == grid[i].length1 <= m, n <= 100-100 <= grid[i][j] <= 100
Follow up: Could you find an
O(n + m) solution?Approach Overview
Problem Overview: You get an m x n matrix where every row and column is sorted in non-increasing order. The task is simple: count how many values are negative. Because the matrix is sorted, negative numbers appear grouped toward the right side of rows and toward the bottom of columns. That structure allows faster solutions than checking every element.
Approach 1: Naive Matrix Scan (O(m * n) time, O(1) space)
The straightforward solution iterates through every cell of the matrix and increments a counter whenever the value is less than zero. This uses two nested loops: the outer loop walks through rows and the inner loop scans each column. No additional data structures are required, so the space complexity stays O(1). This works for any matrix, sorted or not, but it ignores the ordering property and therefore performs unnecessary checks.
Approach 2: Binary Search on Each Row (O(m log n) time, O(1) space)
Each row is sorted in non-increasing order. That means positive numbers appear first, followed by zeros (if any), and all negative numbers appear at the end. For every row, run binary search to find the first index where the value becomes negative. Once that index is located, the remaining elements in that row are guaranteed to be negative, so you add n - index to the total count. This approach reduces unnecessary comparisons and leverages the sorted property effectively.
The algorithm iterates over rows, applies binary search within each row, and accumulates the number of negatives. Because each search takes O(log n) time and runs for m rows, the total complexity becomes O(m log n). Space usage remains constant since only a few pointers are maintained during the search.
This solution highlights a classic application of binary search on sorted data. The matrix structure also connects closely with common patterns from array traversal and matrix processing problems.
Recommended for interviews: Start with the naive scan to demonstrate correctness and baseline reasoning. Then move to the binary search approach, which interviewers typically expect once you recognize the sorted rows. The optimized solution shows you can exploit ordering properties to reduce time complexity.
Approach 1: Naive Approach
The naive approach is to iterate over every element of the matrix and count the negative numbers. Since the matrix dimensions are at most 100x100, this method is feasible but not the most efficient. However, this approach is simple to implement and understand.
This C code iterates through each element of the matrix, checking if it is negative. If an element is negative, it increments the count. This is a straightforward implementation of the problem statement.
Complexity
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1) as we are using constant extra space.
Approach 2: Optimized Binary Search Approach
Utilizing the sorted nature of the matrix, start from the bottom-left or top-right corner to efficiently count negative numbers. You only need to traverse the elements once, either moving inward along a row or column while counting negatives. This can reduce the time complexity to O(n + m), significantly improving performance for large matrices.
This C solution leverages the sorted nature by starting from the top-right corner. It moves left if the current number is negative, counting all numbers below, and down if it is non-negative.
Complexity
Time Complexity: O(n + m)
Space Complexity: O(1)
Approach 3: 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).
If the element at the current position is greater than or equal to 0, it means all preceding elements in that row are also greater than or equal to 0. Therefore, we move the column index j one position to the right, i.e., j = j + 1.
If the element at the current position is less than 0, it means the current element and all elements to its right in that row are negative. Therefore, we can add n - j to the count of negative numbers (where n is the number of columns in the matrix), and then move the row index i one position upward, i.e., i = i - 1.
We repeat the above process until the row index i is less than 0 or the column index j is greater than or equal to n. Finally, the count of negative numbers is the answer.
The time complexity is O(m + n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Binary Search Approach | Time Complexity: |
| Traverse from the Bottom-Left Corner | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Matrix Scan | O(m * n) | O(1) | When the matrix is small or not guaranteed to be sorted |
| Binary Search per Row | O(m log n) | O(1) | When each row is sorted and you want a faster solution for larger matrices |
Video Solution
Count Negative Numbers in a Sorted Matrix || Binary Search || 2 Pointers || Leetcode 1351 • Aryan Mittal • 7,587 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Negative Numbers in a Sorted Matrix easy or hard?
Count Negative Numbers in a Sorted Matrix Python/Java solution
How to solve Count Negative Numbers in a Sorted Matrix in O(m log n)?
What is the best approach for Count Negative Numbers in a Sorted Matrix?
Is Count Negative Numbers in a Sorted Matrix asked at Google/Amazon/Meta?
What data structure is used in Count Negative Numbers in a Sorted Matrix?
What is the time complexity of Count Negative Numbers in a Sorted Matrix?
Ready to solve this problem?
Practice Count Negative Numbers in a Sorted Matrix with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor