Leetcode – Count Negative Numbers in a Sorted Matrix Solution

Spread the love

In this comprehensive article, we will discuss the “Count Negative Numbers in a Sorted Matrix” problem statement, analyze its constraints, and explore multiple solutions, each with its own time and space complexities.

Problem Statement

The problem can be found on Leetcode and is stated as follows:

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.

Examples:

Input: grid = [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]]
Output: 8

Input: grid = [[3, 2], [1, 0]]
Output: 0

Input: grid = [[1, -1], [-1, -1]]
Output: 3

Approaches to Solve the Problem

Brute-force Approach

The most straightforward approach is to traverse the entire matrix and count the number of negative numbers. Given the constraints, this approach would still perform well for this problem.

Here’s the Python code for the brute-force approach:

def countNegatives(grid):
    count = 0
    for row in grid:
        for num in row:
            if num < 0:
                count += 1
    return count

Time Complexity: O(m×n)
Space Complexity: O(1)

Optimized Approach Using Binary Search

Since each row and column are sorted in non-increasing order, we can use binary search to find the first negative number in each row and then calculate how many negative numbers are present in that row. This would optimize the algorithm significantly.

Here is the Python code for this approach:

import bisect

def countNegatives(grid):
    count = 0
    for row in grid:
        index = bisect.bisect_left(row, 0)
        count += len(row) - index
    return count

Time Complexity: O(m × log⁡ n)
Space Complexity: O(1)

Further Optimized Approach Using Reverse Traversal

We can traverse the matrix from the bottom-right corner to the top-left corner, making use of the sorted properties of the rows and columns. Whenever we encounter a negative number, we know that all the numbers above it in the same column will also be negative.

Here’s the Python code for this approach:

def countNegatives(grid):
    count = 0
    m, n = len(grid), len(grid[0])
    i, j = m - 1, 0
    
    while i >= 0 and j < n:
        if grid[i][j] < 0:
            count += (n - j)
            i -= 1
        else:
            j += 1
    return count

Time Complexity: O(m+n)
Space Complexity: O(1)

Why These Approaches Work

Brute-force Approach

The brute-force approach works because it exhaustively checks every single element in the matrix. While it’s not the most efficient method, it’s straightforward and works within the given constraints.

Optimized Approach Using Binary Search

The binary search approach takes advantage of the sorted nature of the matrix. By finding the index of the first negative number in each row, we can easily determine the number of negative numbers in that row without checking each element.

Further Optimized Approach Using Reverse Traversal

The reverse traversal method also capitalizes on the sorted nature of the matrix. It saves time by avoiding the traversal of elements that are guaranteed to be positive based on the elements already checked.

Edge Cases

  1. All Positive or All Negative Matrix: The function should be able to handle cases where all elements are either positive or negative.
  2. Single Row or Single Column Matrices: The function should work for m=1 or n=1.

Conclusion

The “Count Negative Numbers in a Sorted Matrix” problem is an excellent exercise in understanding how to traverse a 2D array efficiently. It offers multiple approaches, each with its own set of trade-offs in terms of time and space complexity. While the brute-force approach is the simplest to understand and implement, the optimized methods show how a deep understanding of the problem and its constraints can lead to more efficient solutions.

Leave a Reply