Count Negative Numbers in a Sorted Matrix - LeetCode

• Matrix sorted non-increasing both row-wise and column-wise
• Count the negatives

Key idea

• Each row is sorted descending, so negatives form a contiguous tail
• Binary search each row for the index of the first negative, then the tail length is the count
• 0 is not negative, so it goes in the same branch as positives

int countNegatives(vector<vector<int>>& grid) {
    int negatives = 0;
    for (auto& row : grid) {
        int left = 0, right = row.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] < 0) {
                right = mid - 1;
            } else {           // >= 0, including 0
                left = mid + 1;
            }
        }
        negatives += row.size() - left;
    }
    return negatives;
}

• left lands on the first negative index, row.size() - left is the count

Bugs I hit

• right = row.size() instead of row.size() - 1, out of bounds on the first row[mid]
• Used row[mid] <= 0 to push right left, which counts 0 as negative

Follow up

• Problem asks for O(n + m), this is O(m log n)
• Staircase walk from the bottom-left corner gets O(n + m), not done yet