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] <= 100Follow up: Could you find an
O(n + m) solution?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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Optimized Binary Search Approach | Time Complexity: |
LeetCode 176 Problem 1 - Count Negative Numbers in a Sorted Matrix • code_report • 8,906 views views
Watch 9 more video solutions →Practice Count Negative Numbers in a Sorted Matrix with our built-in code editor and test cases.
Practice on FleetCode