Count Negative Numbers in a Sorted Matrix — Solution
Count Negative Numbers in a Sorted Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Negative Numbers in a Sorted Matrix is an easy coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Binary Search, Matrix
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m × n matrix grid sorted in non-increasing order both row-wise and column-wise, return the number of negative values it contains.
Example 1
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Example 2
Input: grid = [[3,2],[1,0]]
Output: 0
Example 3
Input: grid = [[-1]]
Output: 1
Constraints
1 <= grid.length, grid[i].length <= 8-100 <= grid[i][j] <= 100grid is sorted non-increasing along rows and columns.
Follow-up: Counting every cell is O(m·n). The double sortedness allows O(m + n).
Hints for Count Negative Numbers in a Sorted Matrix
Hint 1
The straightforward count works, but ignores the structure you were given.
Hint 2
Start at the bottom-left corner. A negative there means the whole rest of that row is negative — add them all and move up.
Hint 3
A non-negative there means step right. Each step consumes a row or a column, so the walk is O(m + n).
How to solve Count Negative Numbers in a Sorted Matrix
Start at the bottom-left corner: a negative there means the rest of its row is negative (add them all, move up); otherwise step right. Each step retires a row or a column.
Approach
- Set
r = m - 1,c = 0. - If
grid[r][c] < 0, addn - cand decrementr; else incrementc. - Stop when
r < 0orc == n.
Why it works
Rows are non-increasing, so once a negative appears in a row everything to its right is negative; columns are non-increasing, so if (r, c) is non-negative, so is every cell above it in that column, which is why moving right never misses anything.
Complexity
- Time —
O(m + n) - Space —
O(1)
Pitfalls
- Counting every cell is
O(m · n)and correct — the staircase walk is what the sorted structure buys. - Binary search per row gives
O(m log n).
Reference solution
Python
def countNegatives(grid) -> int:
m, n = len(grid), len(grid[0])
r, c = m - 1, 0
count = 0
while r >= 0 and c < n:
if grid[r][c] < 0:
count += n - c
r -= 1
else:
c += 1
return countJava
public static int countNegatives(int[][] grid) {
int m = grid.length, n = grid[0].length;
int r = m - 1, c = 0, count = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) {
count += n - c;
r--;
} else {
c++;
}
}
return count;
}C++
int countNegatives(vector<vector<int>>& grid) {
int m = (int) grid.size(), n = (int) grid[0].size();
int r = m - 1, c = 0, count = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) {
count += n - c;
r--;
} else {
c++;
}
}
return count;
}JavaScript
var countNegatives = function(grid) {
const m = grid.length, n = grid[0].length;
let r = m - 1, c = 0, count = 0;
while (r >= 0 && c < n) {
if (grid[r][c] < 0) {
count += n - c;
r--;
} else {
c++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search