EasyArrayBinary SearchMatrix

Count Negative Numbers in a Sorted Matrix

1 approach, code in every language

You are given a rectangular grid of integers where each row is sorted in non-increasing order from left to right, and each column is sorted in non-increasing order from top to bottom. Determine how many entries in the grid are strictly negative.

Because of the sorted structure, the negative values always cluster toward the bottom-left portion of the grid, which lets you count them without inspecting every cell.

Example 1

Input: grid = [[5, 2, -1], [3, 0, -3], [-2, -4, -6]]

Output: 5

The strictly-negative entries are -1 in the first row, -3 in the second row, and -2, -4, -6 in the third row, which is five cells in total.

Example 2

Input: grid = [[4, 3], [2, 1]]

Output: 0

Every value is positive, so there are no negatives to count.

Constraints

1 <= grid.length, grid[i].length <= 100
-100 <= grid[i][j] <= 100
Each row is sorted in non-increasing order
Each column is sorted in non-increasing order

Staircase Traversal

Start at the bottom-left corner and walk toward the top-right, adding a full tail of negatives whenever the current cell is negative.

Loading animation…

Intuition

Anchor a pointer at the bottom-left cell. If that cell is negative, then every cell to its right in the same row must also be negative because the row decreases left to right; you can add that whole remaining segment at once and move up a row. If the cell is not negative, moving right is pointless from here, so advance the column instead. Each step either climbs a row or shifts a column, so the pointer sweeps a monotone staircase across the grid.

Algorithm walkthrough

1Set row to the last row index and col to 0, and initialize count to 0.
2While row is valid and col is within bounds, look at grid[row][col].
3If it is negative, add (cols - col) to count because the rest of that row is negative too, then decrement row.
4Otherwise increment col to search further right in the higher rows.
5When the walk finishes, count holds the number of negative values.

Implementation

from typing import List


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

Time

O(m + n)

Space

O(1)

The pointer moves up or right at most m + n times, where m and n are the grid dimensions.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Freezing Cells on the Weather Board is our own problem on the technique behind Count Negative Numbers in a Sorted Matrix: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free