What is the time complexity of LeetCode 1351. Count Negative Numbers in a Sorted Matrix?

The Python solution on this page runs in O(m + n), where m and n are the number of rows and columns of the matrix, respectively.

What is the space complexity of LeetCode 1351. Count Negative Numbers in a Sorted Matrix?

The Python solution on this page uses O(1) auxiliary space.

Count Negative Numbers in a Sorted Matrix — LeetCode 1351 Python Solution

EasyArrayBinary SearchMatrix

Problem: #1351
Pattern: Matrix and Grid
Reading time: 2 min
Source: leetcode.com

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

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.

Python solution

Python

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:
                j += 1
            else:
                ans += n - j
                i -= 1
        return ans

Complexity

Measure	Complexity
Time	O(m + n), where m and n are the number of rows and columns of the matrix, respectively
Space	O(1) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1351. Count Negative Numbers in a Sorted Matrix is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1351. Count Negative Numbers in a Sorted Matrix?: LeetCode 1351. Count Negative Numbers in a Sorted Matrix is rated Easy on LeetCode.
What is the time complexity of LeetCode 1351. Count Negative Numbers in a Sorted Matrix?: The Python solution on this page runs in O(m + n), where m and n are the number of rows and columns of the matrix, respectively.
What is the space complexity of LeetCode 1351. Count Negative Numbers in a Sorted Matrix?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1351. Count Negative Numbers in a Sorted Matrix cover?: LeetCode 1351. Count Negative Numbers in a Sorted Matrix is tagged Array, Binary Search and Matrix on LeetCode.