We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Negative Numbers in a Sorted Matrix

Number: 1476

Difficulty: Easy

Paid? No

Companies: Meta, Amazon, Bloomberg, Google

Problem Description

Given an m x n matrix grid that is sorted in non-increasing order both row-wise and column-wise, count and return the number of negative numbers in grid.

Key Insights

  • Each row is sorted in non-increasing order, meaning that once a negative number is encountered, all elements to its right in that row are also negative.
  • The matrix’s columns are also sorted in non-increasing order, allowing an efficient traversal starting from a strategic position.
  • The optimal O(m + n) approach starts from the bottom-left of the matrix and moves either up or right based on the sign of the current element.
  • If the current element is negative, all elements to its right in that row are negative; if it is non-negative, move right.

Space and Time Complexity

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

Solution

We use the bottom-left traversal method. Start at the bottom-left cell of the matrix. If the current value is negative, then all elements to its right are negative because the row is sorted; hence, add the count of these negatives and move one row up. If the value is non-negative, move one column to the right. Continue this process until the pointers leave the bounds of the matrix. This approach ensures we count all negative numbers efficiently in O(m + n) time with constant extra space.

Code Solutions

def countNegatives(grid):
    # Get the number of rows and columns
    rows = len(grid)
    cols = len(grid[0])
    count = 0
    # Start from the bottom-left element
    row, col = rows - 1, 0
    while row >= 0 and col < cols:
        # If the current element is negative,
        # add all numbers to its right as negatives in this row.
        if grid[row][col] < 0:
            count += (cols - col)
            # Move one row up as the entire remainder of the row is negative.
            row -= 1
        else:
            # Move right if the current element is non-negative.
            col += 1
    return count

# Example usage:
grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
print(countNegatives(grid))  # Output: 8
← Back to All Questions