1351. Count Negative Numbers in a Sorted Matrix

In this Leetcode problem, we need to count the number of negative numbers in a sorted matrix.

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Problem statement

Solution

The idea is similar to counting negative numbers in a sorted array. To do that, we only need to do a binary search on the array and find the border between negative and positive numbers.

For this problem, we pick the middle row and count the negative numbers in that sorted array. Then we notice that for the first negative numbers in that row, all the values at the bottom right of it are negative, and all the numbers at the top left of it are positive. Then we can do a recursion to count the negative numbers on the top right and the bottom left.

Recursion schema

In that schema, we would add all the green zone to the su of results and recurse on the 2 blue zones.

Here is the solution in Java:

class Solution {
    public int countNegatives(int[][] grid) {
        return countNegativesRec(…