Count Negative Numbers in a Sorted Matrix solution and explanation
Google
9 more videos on this problem
Count Negative Numbers in a Sorted Matrix || Binary Search || 2 Pointers || Leetcode 1351Aryan Mittal · 11:10 · 7K views
Count Negative Numbers in a Sorted Matrix | Leet code 1351 | Theory explained + Python codeSai Anish Malla · 9:48 · 5K views
1351. Count Negative Numbers in a Sorted Matrix | PythonSoumil Shah · 8:03 · 2K views
LeetCode 1351 : Count Negative Numbers in a Sorted Matrix | Solution in JAVAAmit Manjarly · 8:36 · 899 views
Count Negative Numbers in a Sorted Matrix - LeetCode 1351- PythonAlpha-Code · 10:24 · 727 views
1351. Count Negative Numbers in a Sorted Matrix | Leetcode Daily - PythonLeetcode Daily · 9:41 · 690 views
Count Negative Numbers in a Sorted Matrix with Python, JavaScript, Java and C++ - LeetCode #1351CodingNinja · 11:39 · 407 views
Count Negative Numbers in a Sorted Matrix | LeetCode 1351 | Optimal O(N + M) Staircase SearchSanyam IIT Guwahati · 7:33 · 403 views
LeetCode 1351: Count Negative Numbers in a Sorted Matrix | C# Solution | Binary SearchCode Scribbler · 4:36 · 231 views
1351. Count Negative Numbers in a Sorted Matrix with Python #leetcode #pythontutorial #youtube #techArsalan Ahmed · 5:50 · 190 views
The problem
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
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.
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
return sum(1 for row in grid for num in row if num < 0)class Solution {
public int countNegatives(int[][] grid) {
int count = 0;
for (int[] row : grid) {
for (int num : row) {
if (num < 0) {
count++;
}
}
}
return count;
}
}#include <vector>
using namespace std;
int countNegatives(vector<vector<int>>& grid) {
int count = 0;
for (const auto& row : grid) {
for (int num : row) {
if (num < 0) {
count++;
}
}
}
return count;
}var countNegatives = function(grid) {
let count = 0;
for (let row of grid) {
for (let num of row) {
if (num < 0) {
count++;
}
}
}
return count;
};#include <stdio.h>
int countNegatives(int** grid, int gridSize, int* gridColSize) {
int count = 0;
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] < 0) {
count++;
}
}
}
return count;
}public class Solution {
public int CountNegatives(int[][] grid) {
int count = 0;
foreach (var row in grid) {
foreach (var num in row) {
if (num < 0) {
count++;
}
}
}
return count;
}
}In Python, list comprehensions and generator expressions are used to make the code concise. The expression iterates over all elements and counts the negatives.
Time Complexity: O(m * n)
Space Complexity: O(1)
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.
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
count, m, n = 0, len(grid), len(grid[0])
row, col = 0, n - 1
while row < m and col >= 0:
if grid[row][col] < 0:
count += (m - row)
col -= 1
else:
row += 1
return countclass Solution {
public int countNegatives(int[][] grid) {
int count = 0;
int m = grid.length, n = grid[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (grid[row][col] < 0) {
count += m - row;
col--;
} else {
row++;
}
}
return count;
}
}#include <vector>
using namespace std;
int countNegatives(vector<vector<int>>& grid) {
int count = 0;
int m = grid.size(), n = grid[0].size();
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (grid[row][col] < 0) {
count += (m - row);
col--;
} else {
row++;
}
}
return count;
}var countNegatives = function(grid) {
let count = 0;
let m = grid.length, n = grid[0].length;
let row = 0, col = n - 1;
while (row < m && col >= 0) {
if (grid[row][col] < 0) {
count += (m - row);
col--;
} else {
row++;
}
}
return count;
};#include <stdio.h>
int countNegatives(int** grid, int gridSize, int* gridColSize) {
int count = 0;
int m = gridSize, n = gridColSize[0];
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (grid[row][col] < 0) {
count += (m - row);
col--;
} else {
row++;
}
}
return count;
}public class Solution {
public int CountNegatives(int[][] grid) {
int count = 0;
int m = grid.Length, n = grid[0].Length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (grid[row][col] < 0) {
count += m - row;
col--;
} else {
row++;
}
}
return count;
}
}In Python, the logic is implemented similarly by starting at the top-right and traversing intelligently, counting negatives by rows when feasible.
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).
function countNegatives(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
let i = m - 1;
let j = 0;
let ans = 0;
while (i >= 0 && j < n) {
if (grid[i][j] >= 0) {
j++;
} else {
ans += n - j;
i--;
}
}
return ans;
}func countNegatives(grid [][]int) (ans int) {
m := len(grid)
n := len(grid[0])
i := m - 1
j := 0
for i >= 0 && j < n {
if grid[i][j] >= 0 {
j++
} else {
ans += n - j
i--
}
}
return
}impl Solution {
pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut i: i32 = m as i32 - 1;
let mut j: usize = 0;
let mut ans: i32 = 0;
while i >= 0 && j < n {
if grid[i as usize][j] >= 0 {
j += 1;
} else {
ans += (n - j) as i32;
i -= 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Binary Search Approach | Time Complexity: |
| Traverse from the Bottom-Left Corner | – |
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 |
Frequently asked questions
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).