# Count Negative Numbers in a Sorted Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix)
Canonical: https://scaleengineer.com/dsa/problems/count-negative-numbers-in-a-sorted-matrix
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Matrix
---
## Problem
Given a `m x n` matrix `grid` which is sorted in non-increasing order both row-wise and column-wise, return _the number of **negative** numbers in_ `grid`.

**Example 1:**

**Input:** grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
**Output:** 8
**Explanation:** There are 8 negatives number in the matrix.

**Example 2:**

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

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 100`
* `-100 <= grid[i][j] <= 100`

**Follow up:** Could you find an `O(n + m)` solution?

# Approaches
## Brute Force Iteration
The brute-force approach is the most straightforward way to solve the problem. It involves iterating through every single cell of the `m x n` matrix, checking if the value in the cell is negative, and incrementing a counter if it is. This method is easy to understand and implement but ignores the valuable information that the matrix is sorted both row-wise and column-wise.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. This is because we must visit every element in the matrix once. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Very simple to understand and implement.; Works for any matrix, regardless of whether it's sorted or not.
**Cons:** This is the least efficient approach as it does not utilize the sorted property of the matrix at all.; For large matrices, this approach will be significantly slower than more optimized solutions.
### Explanation
In this method, we simply treat the matrix as an unsorted 2D array. We start by initializing a counter variable, say `count`, to zero. Then, we set up two nested loops to traverse the matrix. The outer loop iterates through the rows (from 0 to `m-1`), and the inner loop iterates through the columns (from 0 to `n-1`). Inside the inner loop, we access the element `grid[row][col]` and check if its value is negative (i.e., less than 0). If it is, we increment our `count`. After the loops have finished checking every element, the `count` variable will hold the total number of negative numbers, and we return this value.

```java
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] < 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use nested loops to iterate through each element of the `m x n` matrix.
- The outer loop runs from `row = 0` to `m-1`.
- The inner loop runs from `col = 0` to `n-1`.
- For each element `grid[row][col]`, check if it is less than 0.
- If `grid[row][col] < 0`, increment the `count`.
- After iterating through all elements, return the final `count`.

## Binary Search on Each Row
A more optimized approach leverages the fact that each row is sorted in non-increasing order. For any given row, all the negative numbers will be clustered at the end. This structure allows us to use binary search on each row to find the first occurrence of a negative number. Once we find the index of the first negative number, say `k`, we know that all `n - k` elements from that index to the end of the row are negative.
**Time:** O(m * log n). We iterate through `m` rows, and for each row, we perform a binary search which takes O(log n) time. · **Space:** O(1), as no extra data structures are needed. The space used is constant.
**Pros:** Significantly more efficient than the brute-force approach for matrices with many columns.; Effectively uses the row-wise sorted property.
**Cons:** This approach does not utilize the column-wise sorted property of the matrix, which prevents it from achieving the optimal time complexity.
### Explanation
We iterate through each of the `m` rows. For each row, instead of a linear scan, we apply binary search to find the boundary between non-negative and negative numbers. The goal of the binary search is to find the index of the leftmost negative number. If such a number is found at index `k`, then we know there are `n - k` negative numbers in that row. If no negative numbers exist in a row, the binary search will conclude without finding one, and we add 0 to our total for that row. We sum the counts from each row to get the final answer.

This helper function `binarySearchForRow` finds the number of negative elements in a single row.

```java
class Solution {
    public int countNegatives(int[][] grid) {
        int count = 0;
        for (int[] row : grid) {
            count += binarySearchForRow(row);
        }
        return count;
    }

    private int binarySearchForRow(int[] row) {
        int low = 0;
        int high = row.length - 1;
        // We are looking for the first index 'low' where row[low] < 0
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (row[mid] < 0) {
                // This could be the first negative, or there could be more to the left.
                // So we check the left part.
                high = mid - 1;
            } else {
                // The element is non-negative, so the first negative must be to the right.
                low = mid + 1;
            }
        }
        // 'low' is the index of the first negative number.
        // The number of negative elements is the total length minus this index.
        return row.length - low;
    }
}
```
### Algorithm
- Initialize a total count `totalCount` to 0.
- Iterate through each row of the matrix from `i = 0` to `m-1`.
- For each row, perform a binary search to find the index of the first negative number.
- In the binary search for a row, if `grid[i][mid]` is negative, it means this and all subsequent elements in the row are negative. We record this count and continue searching in the left half (`[low, mid-1]`) for an even earlier negative number.
- If `grid[i][mid]` is non-negative, the first negative number must be in the right half (`[mid+1, high]`).
- The number of negative elements in the current row is `n - low` after the binary search loop finishes (where `low` is the insertion point for negative numbers).
- Add the count of negative numbers for the current row to `totalCount`.
- Return `totalCount` after iterating through all rows.

## Optimal Staircase Search
The most efficient solution, often called the Staircase Search or Search Space Reduction, takes full advantage of the matrix being sorted both row-wise and column-wise. By starting at a specific corner (e.g., top-right or bottom-left), we can eliminate either a row or a column in each step, allowing us to traverse the matrix in linear time relative to its dimensions.
**Time:** O(m + n). In each step of the while loop, we either increment `row` or decrement `col`. The `row` pointer moves from `0` to `m`, and the `col` pointer moves from `n-1` to `-1`. The total number of steps is bounded by the sum of the number of rows and columns. · **Space:** O(1), as it only requires a few variables to store the pointers and the count.
**Pros:** Optimal time complexity of O(m + n).; Very efficient in terms of space, using only O(1) extra space.; Cleverly utilizes both row and column sorted properties.
**Cons:** The logic can be slightly less intuitive to come up with compared to the more straightforward approaches.
### Explanation
We can visualize this approach as tracing a path on the matrix that separates the non-negative numbers from the negative numbers. Let's start at the top-right corner `(row = 0, col = n - 1)`.

At each step, we examine `grid[row][col]`:
1.  If the element is **negative**, we know that every element below it in the current column must also be negative (due to column-wise sorting). So, we've found `m - row` negative numbers in this column. We add this to our count and move one column to the left (`col--`) to continue our search in the same row.
2.  If the element is **non-negative**, we know that every element to its left in the current row must also be non-negative (due to row-wise sorting). Therefore, there are no negative numbers left to be found in this row. We can effectively discard this row and move down to the next one (`row++`) to continue the search.

This process continues until our pointers move out of the matrix bounds. Because in each step we either increment `row` or decrement `col`, the total number of steps is at most `m + n`.

```java
class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (grid[row][col] < 0) {
                // All elements in this column from the current row down are negative.
                count += (m - row);
                // Move to the previous column to find more negatives.
                col--;
            } else {
                // This element is non-negative, so no negatives in this row to the left.
                // Move to the next row.
                row++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Get the matrix dimensions, `m` (rows) and `n` (columns).
- Initialize a counter `count` to 0.
- Start at the top-right corner of the matrix by setting `row = 0` and `col = n - 1`.
- Loop as long as the pointers are within the matrix bounds (`row < m` and `col >= 0`).
- Check the value of `grid[row][col]`:
  - If `grid[row][col] < 0`: The current element is negative. Since the column is sorted non-increasingly, all elements below it in the same column are also negative. There are `m - row` such elements. Add this to `count` and move to the previous column (`col--`) to find more negatives.
  - If `grid[row][col] >= 0`: The current element is non-negative. Since the row is sorted non-increasingly, all elements to its left in the same row are also non-negative. Thus, we can discard the current row from consideration and move down to the next row (`row++`).
- The loop terminates when `row` or `col` goes out of bounds. Return the final `count`.

# Solutions
### Java

```java
class Solution {
public
  int countNegatives(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int ans = 0;
    for (int i = m - 1, j = 0; i >= 0 && j < n;) {
      if (grid[i][j] < 0) {
        ans += n - j;
        --i;
      } else {
        ++j;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var countNegatives =
  function (grid) {
    const m = grid.length,
      n = grid[0].length;
    let ans = 0;
    for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
      if (grid[i][j] < 0) {
        ans += n - j;
        --i;
      } else {
        ++j;
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int countNegatives(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    for (int i = m - 1, j = 0; i >= 0 && j < n;) {
      if (grid[i][j] < 0) {
        ans += n - j;
        --i;
      } else
        ++j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) i, j = m - 1, 0 ans = 0 while i >= 0 and j < n: if grid[i][j] < 0: ans += n - j i -= 1 else: j += 1 return ans

```