Count Negative Numbers in a Sorted Matrix

Easy
281.

Count Negative Numbers in a Sorted Matrix

Count Negative Numbers in a Sorted Matrix is an easy coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

Given an m × n matrix grid sorted in non-increasing order both row-wise and column-wise, return the number of negative values it contains.

Example 1

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

Example 2

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

Example 3

Input
grid = [[-1]]
Output
1

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • -100 <= grid[i][j] <= 100
  • grid is sorted non-increasing along rows and columns.

Follow-up: Counting every cell is O(m·n). The double sortedness allows O(m + n).

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Negative Numbers in a Sorted Matrix — Solution

Count Negative Numbers in a Sorted Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Negative Numbers in a Sorted Matrix is an easy coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given an m × n matrix grid sorted in non-increasing order both row-wise and column-wise, return the number of negative values it contains.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • -100 <= grid[i][j] <= 100
  • grid is sorted non-increasing along rows and columns.

Follow-up: Counting every cell is O(m·n). The double sortedness allows O(m + n).

Hints for Count Negative Numbers in a Sorted Matrix

  1. Hint 1

    The straightforward count works, but ignores the structure you were given.

  2. Hint 2

    Start at the bottom-left corner. A negative there means the whole rest of that row is negative — add them all and move up.

  3. Hint 3

    A non-negative there means step right. Each step consumes a row or a column, so the walk is O(m + n).

How to solve Count Negative Numbers in a Sorted Matrix

Start at the bottom-left corner: a negative there means the rest of its row is negative (add them all, move up); otherwise step right. Each step retires a row or a column.

Approach

  1. Set r = m - 1, c = 0.
  2. If grid[r][c] < 0, add n - c and decrement r; else increment c.
  3. Stop when r < 0 or c == n.

Why it works

Rows are non-increasing, so once a negative appears in a row everything to its right is negative; columns are non-increasing, so if (r, c) is non-negative, so is every cell above it in that column, which is why moving right never misses anything.

Complexity

  • Time — O(m + n)
  • Space — O(1)

Pitfalls

  • Counting every cell is O(m · n) and correct — the staircase walk is what the sorted structure buys.
  • Binary search per row gives O(m log n).

Reference solution

Python

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

Java

public static int countNegatives(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int r = m - 1, c = 0, count = 0;
    while (r >= 0 && c < n) {
        if (grid[r][c] < 0) {
            count += n - c;
            r--;
        } else {
            c++;
        }
    }
    return count;
}

C++

int countNegatives(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    int r = m - 1, c = 0, count = 0;
    while (r >= 0 && c < n) {
        if (grid[r][c] < 0) {
            count += n - c;
            r--;
        } else {
            c++;
        }
    }
    return count;
}

JavaScript

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let r = m - 1, c = 0, count = 0;
    while (r >= 0 && c < n) {
        if (grid[r][c] < 0) {
            count += n - c;
            r--;
        } else {
            c++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search