Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix - 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.

The matrix is sorted such that:

Each row is sorted in non-increasing order from left to right
Each column is sorted in non-increasing order from top to bottom

This means larger numbers appear in the top-left, and smaller (potentially negative) numbers appear in the bottom-right.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[4,3,-1],[-3,-4,-5]]

› Output: 4

💡 Note: Row 1 has 1 negative number (-1), Row 2 has 3 negative numbers (-3, -4, -5). Total = 1 + 3 = 4

Example 2 — All Positive

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

› Output: 0

💡 Note: All numbers in the matrix are non-negative, so the count is 0

Example 3 — Mixed Pattern

$ Input: grid = [[1,-1],[-1,-1]]

› Output: 3

💡 Note: Row 1 has 1 negative (-1), Row 2 has 2 negatives (-1, -1). Total = 1 + 2 = 3

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 100
-100 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted matrix with decreasing values

Strategy

Use sorting to skip entire regions

Output

Total count of negative numbers

Key Takeaway

🎯 Key Insight: Use the sorted matrix property to eliminate entire rows or columns at once instead of checking every element

Asked in

a Amazon 25 M Microsoft 18 G Google 15

The key insight is to utilize the sorted property of the matrix. The optimal staircase search approach starts from the top-right corner and moves strategically based on the current element's sign. Time: O(m+n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Each Row	O(m×log n)	O(1)	Use binary search to find the first negative number in each row
Staircase Search - Start from Top-Right Corner	O(m+n)	O(1)	Start from top-right corner and move left or down based on current element
Brute Force - Check Every Element	O(m×n)	O(1)	Iterate through every element in the matrix and count negatives

Binary Search on Each Row — Algorithm Steps

For each row in the matrix
Use binary search to find the leftmost negative number
Count all elements from that position to the end of the row
Add the count to the total

Visualization

Tap to expand

Step-by-Step Walkthrough

Row 1

Binary search finds first negative at index 2

Row 2

Binary search finds first negative at index 1

Count

Sum up negatives from each row

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    int count = 0;
    for (int i = 0; i < gridSize; i++) {
        // Binary search for first negative number
        int left = 0, right = gridColSize[i];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (grid[i][mid] < 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // All elements from 'left' to end are negative
        count += gridColSize[i] - left;
    }
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demo
    int grid[100][100];
    int gridSize = 0, gridColSize[100];
    
    // Parse manually (simplified)
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int colCount = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' || *ptr == '-') {
                    grid[gridSize][colCount++] = atoi(ptr);
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                }
                if (*ptr == ',') ptr++;
            }
            gridColSize[gridSize] = colCount;
            gridSize++;
        }
        ptr++;
    }
    
    int* gridPtrs[100];
    for (int i = 0; i < gridSize; i++) {
        gridPtrs[i] = grid[i];
    }
    
    printf("%d\n", solution(gridPtrs, gridSize, gridColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×log n)

For each of m rows, we perform binary search taking O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for binary search variables

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Each Row — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler