Count Negative Numbers in a Sorted Matrix - Video Solutions

Problem Overview: You get an m x n matrix where every row and column is sorted in non-increasing order. The task is simple: count how many values are negative. Because the matrix is sorted, negative numbers appear grouped toward the right side of rows and toward the bottom of columns. That structure allows faster solutions than checking every element.

Approach 1: Naive Matrix Scan (O(m * n) time, O(1) space)

The straightforward solution iterates through every cell of the matrix and increments a counter whenever the value is less than zero. This uses two nested loops: the outer loop walks through rows and the inner loop scans each column. No additional data structures are required, so the space complexity stays O(1). This works for any matrix, sorted or not, but it ignores the ordering property and therefore performs unnecessary checks.

Approach 2: Binary Search on Each Row (O(m log n) time, O(1) space)

Each row is sorted in non-increasing order. That means positive numbers appear first, followed by zeros (if any), and all negative numbers appear at the end. For every row, run binary search to find the first index where the value becomes negative. Once that index is located, the remaining elements in that row are guaranteed to be negative, so you add n - index to the total count. This approach reduces unnecessary comparisons and leverages the sorted property effectively.

The algorithm iterates over rows, applies binary search within each row, and accumulates the number of negatives. Because each search takes O(log n) time and runs for m rows, the total complexity becomes O(m log n). Space usage remains constant since only a few pointers are maintained during the search.

This solution highlights a classic application of binary search on sorted data. The matrix structure also connects closely with common patterns from array traversal and matrix processing problems.

Recommended for interviews: Start with the naive scan to demonstrate correctness and baseline reasoning. Then move to the binary search approach, which interviewers typically expect once you recognize the sorted rows. The optimized solution shows you can exploit ordering properties to reduce time complexity.