LeetCode 1351 - Count Negative Numbers in a Sorted Matrix

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Matrix

Solution

Problem Understanding

The problem asks us to count all the negative numbers in a 2D matrix grid where each row and column is sorted in non-increasing order. In other words, values decrease or stay the same as you move to the right in a row and downward in a column. The input is a matrix of integers, and the output is a single integer representing how many elements in the matrix are negative.

The constraints indicate that the matrix can be as large as 100x100, so up to 10,000 elements. Each element is bounded between -100 and 100. The sorting property is key and allows us to avoid checking every element individually for negatives.

Important edge cases include matrices with all positive numbers, all negative numbers, a single row or column, and a matrix where negatives only appear at the bottom-right corner. The guarantee of non-increasing order simplifies searching since once a negative is found in a row, all elements to the right are also negative, and once a negative is found in a column, all elements below that in the same column are also negative.

Approaches

A brute-force approach would iterate through every element in the matrix, count if it is negative, and sum the results. This is simple and always correct but inefficient, especially for larger matrices, because it does not exploit the sorted property.

The optimal approach uses the sorted property. By starting from the top-right corner, we can traverse the matrix in O(n + m) time. If the current number is negative, all elements below in the same column are negative, so we count them and move left. If the current number is non-negative, we move down to the next row. This efficiently skips large portions of the matrix and ensures we count all negatives without unnecessary checks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(1)	Check each element individually
Optimal	O(m + n)	O(1)	Start from top-right and traverse using the sorted property

Algorithm Walkthrough

Initialize a counter count to 0. This will store the total number of negative numbers.
Set your starting position at the top-right element of the matrix: row = 0, col = n - 1.
While row is within bounds and col is within bounds:
If the current element grid[row][col] is negative:
All elements below this one in the same column are negative because the column is sorted.
Add (m - row) to count since m - row elements are below and including the current element.
Move left by decrementing col to check the next column.
Otherwise, if the current element is non-negative:
Move down by incrementing row to check the next row.
Continue until you either move past the last row or the first column.
Return count.

Why it works: The algorithm leverages the sorted property. Starting from the top-right ensures that moving left encounters smaller numbers and moving down encounters smaller numbers in the column. This guarantees that we count all negative numbers exactly once without revisiting elements.

Python Solution

from typing import List

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row, col = 0, n - 1
        count = 0
        
        while row < m and col >= 0:
            if grid[row][col] < 0:
                count += m - row
                col -= 1
            else:
                row += 1
        
        return count

This implementation initializes pointers at the top-right corner. The while loop navigates the matrix based on the value at the current position. Negative values increment the count by all remaining rows below and then move left, while non-negative values move downward. The loop continues until all rows and columns are traversed efficiently.

Go Solution

func countNegatives(grid [][]int) int {
    m := len(grid)
    if m == 0 {
        return 0
    }
    n := len(grid[0])
    row, col := 0, n - 1
    count := 0

    for row < m && col >= 0 {
        if grid[row][col] < 0 {
            count += m - row
            col--
        } else {
            row++
        }
    }

    return count
}

The Go solution follows the same logic as the Python solution. The len function determines the number of rows and columns. The traversal uses a for loop with row and col pointers, incrementing count whenever a negative element is encountered. Go handles slices efficiently, and integer overflow is not a concern for the given constraints.

Worked Examples

Example 1: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Start at top-right (0,3 = -1). Count = 4 (all rows below including this). Move left to (0,2 = 2). Not negative, move down (1,2 = 1). Not negative, move down (2,2 = -1). Count += 2 (rows 2 and 3), move left (2,1 = 1), move down (3,1 = -1), count += 1. Total = 8.

Example 2: grid = [[3,2],[1,0]]

Top-right (0,1 = 2). Not negative, move down (1,1 = 0). Not negative, move down (2,1). Out of bounds, stop. Count = 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	Each row and column is visited at most once
Space	O(1)	Only a few integer variables are used

The traversal never revisits any cell, ensuring linear time relative to the sum of rows and columns. Space usage is constant.

Test Cases

# Provided examples
assert Solution().countNegatives([[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]) == 8  # mix of positives and negatives
assert Solution().countNegatives([[3,2],[1,0]]) == 0  # all non-negative

# Edge cases
assert Solution().countNegatives([[-1]]) == 1  # single negative element
assert Solution().countNegatives([[1]]) == 0  # single non-negative element
assert Solution().countNegatives([[0]]) == 0  # single zero element
assert Solution().countNegatives([[5,3,0], [3,2,-1], [1,-1,-2]]) == 4  # mixed small 3x3
assert Solution().countNegatives([[-3,-2,-1],[-2,-1,-1],[-1,-1,-1]]) == 9  # all negative
assert Solution().countNegatives([[100]*100]) == 0  # large row, all positive
assert Solution().countNegatives([[-100]*100]) == 100  # large row, all negative

Test	Why
Provided example with mixed negatives	Validates correct counting in typical case
Provided example with all positives	Ensures zero negatives handled
Single element negative	Edge case of 1x1 negative
Single element non-negative	Edge case of 1x1 non-negative
Single zero	Tests that zero is not counted as negative
Mixed small 3x3	Validates algorithm with small mixed numbers
All negative	Validates algorithm counts all negatives
Large row, all positive	Tests performance for large input without negatives
Large row, all negative	Tests performance for large input with all negatives

Edge Cases

The first important edge case is a matrix with only one element, either negative, zero, or positive. This tests that the algorithm correctly handles the smallest possible input without errors and counts negatives accurately.

The second edge case is a matrix where negatives only appear in the bottom-right corner. Naive approaches may unnecessarily traverse the top-left portion, but the optimal algorithm jumps efficiently based on the sorted property and counts negatives without extra iterations.

The third edge case is a matrix where all elements are negative or all are non-negative. The first ensures that the algorithm correctly counts every element without skipping, and the second ensures that the algorithm returns zero correctly. Both cases confirm that the traversal logic respects matrix boundaries and does not produce off-by-one errors.