Count Negative Numbers in a Sorted Matrix
EasyPrompt
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?Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves iterating through every single cell of the m x n matrix, checking if the value in the cell is negative, and incrementing a counter if it is. This method is easy to understand and implement but ignores the valuable information that the matrix is sorted both row-wise and column-wise.
Algorithm
- Initialize a counter
countto 0. - Use nested loops to iterate through each element of the
m x nmatrix. - The outer loop runs from
row = 0tom-1. - The inner loop runs from
col = 0ton-1. - For each element
grid[row][col], check if it is less than 0. - If
grid[row][col] < 0, increment thecount. - After iterating through all elements, return the final
count.
Walkthrough
In this method, we simply treat the matrix as an unsorted 2D array. We start by initializing a counter variable, say count, to zero. Then, we set up two nested loops to traverse the matrix. The outer loop iterates through the rows (from 0 to m-1), and the inner loop iterates through the columns (from 0 to n-1). Inside the inner loop, we access the element grid[row][col] and check if its value is negative (i.e., less than 0). If it is, we increment our count. After the loops have finished checking every element, the count variable will hold the total number of negative numbers, and we return this value.
class Solution { public int countNegatives(int[][] grid) { int m = grid.length; int n = grid[0].length; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] < 0) { count++; } } } return count; }}Complexity
Time
O(m * n), where `m` is the number of rows and `n` is the number of columns. This is because we must visit every element in the matrix once.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Very simple to understand and implement.
Works for any matrix, regardless of whether it's sorted or not.
Cons
This is the least efficient approach as it does not utilize the sorted property of the matrix at all.
For large matrices, this approach will be significantly slower than more optimized solutions.
A more optimized approach leverages the fact that each row is sorted in non-increasing order. For any given row, all the negative numbers will be clustered at the end. This structure allows us to use binary search on each row to find the first occurrence of a negative number. Once we find the index of the first negative number, say k, we know that all n - k elements from that index to the end of the row are negative.
Algorithm
- Initialize a total count
totalCountto 0. - Iterate through each row of the matrix from
i = 0tom-1. - For each row, perform a binary search to find the index of the first negative number.
- In the binary search for a row, if
grid[i][mid]is negative, it means this and all subsequent elements in the row are negative. We record this count and continue searching in the left half ([low, mid-1]) for an even earlier negative number. - If
grid[i][mid]is non-negative, the first negative number must be in the right half ([mid+1, high]). - The number of negative elements in the current row is
n - lowafter the binary search loop finishes (wherelowis the insertion point for negative numbers). - Add the count of negative numbers for the current row to
totalCount. - Return
totalCountafter iterating through all rows.
Walkthrough
We iterate through each of the m rows. For each row, instead of a linear scan, we apply binary search to find the boundary between non-negative and negative numbers. The goal of the binary search is to find the index of the leftmost negative number. If such a number is found at index k, then we know there are n - k negative numbers in that row. If no negative numbers exist in a row, the binary search will conclude without finding one, and we add 0 to our total for that row. We sum the counts from each row to get the final answer.
This helper function binarySearchForRow finds the number of negative elements in a single row.
class Solution { public int countNegatives(int[][] grid) { int count = 0; for (int[] row : grid) { count += binarySearchForRow(row); } return count; } private int binarySearchForRow(int[] row) { int low = 0; int high = row.length - 1; // We are looking for the first index 'low' where row[low] < 0 while (low <= high) { int mid = low + (high - low) / 2; if (row[mid] < 0) { // This could be the first negative, or there could be more to the left. // So we check the left part. high = mid - 1; } else { // The element is non-negative, so the first negative must be to the right. low = mid + 1; } } // 'low' is the index of the first negative number. // The number of negative elements is the total length minus this index. return row.length - low; }}Complexity
Time
O(m * log n). We iterate through `m` rows, and for each row, we perform a binary search which takes O(log n) time.
Space
O(1), as no extra data structures are needed. The space used is constant.
Trade-offs
Pros
Significantly more efficient than the brute-force approach for matrices with many columns.
Effectively uses the row-wise sorted property.
Cons
This approach does not utilize the column-wise sorted property of the matrix, which prevents it from achieving the optimal time complexity.
The most efficient solution, often called the Staircase Search or Search Space Reduction, takes full advantage of the matrix being sorted both row-wise and column-wise. By starting at a specific corner (e.g., top-right or bottom-left), we can eliminate either a row or a column in each step, allowing us to traverse the matrix in linear time relative to its dimensions.
Algorithm
- Get the matrix dimensions,
m(rows) andn(columns). - Initialize a counter
countto 0. - Start at the top-right corner of the matrix by setting
row = 0andcol = n - 1. - Loop as long as the pointers are within the matrix bounds (
row < mandcol >= 0). - Check the value of
grid[row][col]:- If
grid[row][col] < 0: The current element is negative. Since the column is sorted non-increasingly, all elements below it in the same column are also negative. There arem - rowsuch elements. Add this tocountand move to the previous column (col--) to find more negatives. - If
grid[row][col] >= 0: The current element is non-negative. Since the row is sorted non-increasingly, all elements to its left in the same row are also non-negative. Thus, we can discard the current row from consideration and move down to the next row (row++).
- If
- The loop terminates when
roworcolgoes out of bounds. Return the finalcount.
Walkthrough
We can visualize this approach as tracing a path on the matrix that separates the non-negative numbers from the negative numbers. Let's start at the top-right corner (row = 0, col = n - 1).
At each step, we examine grid[row][col]:
- If the element is negative, we know that every element below it in the current column must also be negative (due to column-wise sorting). So, we've found
m - rownegative numbers in this column. We add this to our count and move one column to the left (col--) to continue our search in the same row. - If the element is non-negative, we know that every element to its left in the current row must also be non-negative (due to row-wise sorting). Therefore, there are no negative numbers left to be found in this row. We can effectively discard this row and move down to the next one (
row++) to continue the search.
This process continues until our pointers move out of the matrix bounds. Because in each step we either increment row or decrement col, the total number of steps is at most m + n.
class Solution { public int countNegatives(int[][] grid) { int m = grid.length; int n = grid[0].length; int count = 0; int row = 0; int col = n - 1; while (row < m && col >= 0) { if (grid[row][col] < 0) { // All elements in this column from the current row down are negative. count += (m - row); // Move to the previous column to find more negatives. col--; } else { // This element is non-negative, so no negatives in this row to the left. // Move to the next row. row++; } } return count; }}Complexity
Time
O(m + n). In each step of the while loop, we either increment `row` or decrement `col`. The `row` pointer moves from `0` to `m`, and the `col` pointer moves from `n-1` to `-1`. The total number of steps is bounded by the sum of the number of rows and columns.
Space
O(1), as it only requires a few variables to store the pointers and the count.
Trade-offs
Pros
Optimal time complexity of O(m + n).
Very efficient in terms of space, using only O(1) extra space.
Cleverly utilizes both row and column sorted properties.
Cons
The logic can be slightly less intuitive to come up with compared to the more straightforward approaches.
Solutions
Solution
class Solution {public int countNegatives(int[][] grid) { int m = grid.length, n = grid[0].length; int ans = 0; for (int i = m - 1, j = 0; i >= 0 && j < n;) { if (grid[i][j] < 0) { ans += n - j; --i; } else { ++j; } } return ans; }}/** * @param {number[][]} grid * @return {number} */ var countNegatives = function (grid) { const m = grid.length, n = grid[0].length; let ans = 0; for (let i = m - 1, j = 0; i >= 0 && j < n; ) { if (grid[i][j] < 0) { ans += n - j; --i; } else { ++j; } } return ans; };class Solution {public: int countNegatives(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int ans = 0; for (int i = m - 1, j = 0; i >= 0 && j < n;) { if (grid[i][j] < 0) { ans += n - j; --i; } else ++j; } return ans; }};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: ans += n - j i -= 1 else: j += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.