Problem Description

You are given a m x n matrix grid where all elements are sorted in non-increasing order both row-wise and column-wise. This means:

• Each row is sorted from left to right in descending order (or non-increasing order)
• Each column is sorted from top to bottom in descending order (or non-increasing order)

Your task is to count and return the total number of negative numbers present in the entire matrix.

For example, if you have a matrix like:

[[ 4,  3,  2, -1],
 [ 3,  2,  1, -1],
 [ 1,  1, -1, -2],
 [-1, -1, -2, -3]]

Each row decreases from left to right, and each column decreases from top to bottom. The negative numbers in this matrix are: -1, -1, -1, -2, -1, -1, -2, -3, giving us a total count of 8.

The solution leverages the sorted property of the matrix by starting from the bottom-left corner (position [m-1, 0]). It moves strategically:

• When a negative number is found at position [i, j], all elements to its right in that row must also be negative (due to the non-increasing property), so we can count n - j negatives and move up one row
• When a non-negative number is found, we move right one column to continue searching for the boundary between non-negative and negative numbers

This approach efficiently counts all negatives in O(m + n) time complexity by traversing at most m + n cells.

Intuition

The key insight comes from observing the sorted property of the matrix. Since each row and column is sorted in non-increasing order, the negative numbers form a "staircase" pattern in the matrix.

Think about where negative numbers can appear: due to the non-increasing property, once you encounter a negative number in a row, everything to its right must also be negative. Similarly, once you find a negative number in a column, everything below it must also be negative.

This creates a boundary line between non-negative and negative regions that looks like descending stairs when viewed from the top-left to bottom-right.

Why start from the bottom-left corner? This position gives us the perfect vantage point to trace this boundary efficiently:

1. If we find a negative number at position [i, j], we know that all elements to the right (positions [i, j+1] to [i, n-1]) are also negative. We can count all of them at once: n - j negatives.

2. After counting negatives in row i, we move up to row i-1 because we've already accounted for all negatives in the current row.

3. If we find a non-negative number, we need to move right to find where the negatives start in this row.

This approach ensures we visit each row and column at most once, giving us a linear traversal path that follows the "staircase boundary" between positive and negative regions.

Starting from the top-right corner would work equally well with a similar logic - the key is to start from a corner where we can make definitive decisions about entire rows or columns based on a single element.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses a two-pointer technique that traverses the matrix from the bottom-left corner towards the top-right direction.

Algorithm Steps:

1. Initialize variables:

   • m, n = len(grid), len(grid[0]) - Get matrix dimensions
   • i, j = m - 1, 0 - Start from bottom-left corner (last row, first column)
   • ans = 0 - Counter for negative numbers

2. Traverse the matrix:

   • Use a while loop with condition i >= 0 and j < n to stay within bounds
   • This ensures we don't go above the first row (i >= 0) or beyond the last column (j < n)

3. Decision at each position:

   • If grid[i][j] < 0: We found a negative number
     • Add n - j to the answer (all elements from column j to column n-1 in row i are negative)
     • Move up one row: i -= 1 (we've counted all negatives in the current row)
   • Else (grid[i][j] >= 0): Current element is non-negative
     • Move right one column: j += 1 (looking for where negatives start in this row)

4. Return the result:

   • After the loop exits (when we've either reached the top row or rightmost column), return ans

Why this works:

The algorithm traces the boundary between non-negative and negative regions. Due to the sorted property:

• When we find a negative at position [i, j], we can immediately count all elements to its right in that row
• We never need to revisit a row or column we've already processed
• The path we take forms a monotonic traversal from bottom-left to top-right

Time Complexity: O(m + n) - We visit at most m + n cells (moving up at most m times and right at most n times)

Space Complexity: O(1) - Only using a few variables for tracking position and count

Example Walkthrough

Let's trace through a small example to illustrate the solution approach:

grid = [[3,  2, -1],
        [2,  0, -2],
        [1, -1, -3]]

Initial Setup:

• m = 3, n = 3 (3x3 matrix)
• Start at bottom-left: i = 2, j = 0 (position [2,0] with value 1)
• ans = 0

Step 1: At position [2,0], value = 1 (non-negative)

• Since 1 ≥ 0, move right: j = 1
• Current position: [2,1], ans = 0

Step 2: At position [2,1], value = -1 (negative!)

• Since -1 < 0, count all elements from j=1 to n-1=2 in this row
• Add n - j = 3 - 1 = 2 to ans (counting -1 and -3)
• Move up: i = 1
• Current position: [1,1], ans = 2

Step 3: At position [1,1], value = 0 (non-negative)

• Since 0 ≥ 0, move right: j = 2
• Current position: [1,2], ans = 2

Step 4: At position [1,2], value = -2 (negative!)

• Since -2 < 0, count all elements from j=2 to n-1=2 in this row
• Add n - j = 3 - 2 = 1 to ans (counting just -2)
• Move up: i = 0
• Current position: [0,2], ans = 3

Step 5: At position [0,2], value = -1 (negative!)

• Since -1 < 0, count all elements from j=2 to n-1=2 in this row
• Add n - j = 3 - 2 = 1 to ans (counting just -1)
• Move up: i = -1
• ans = 4

Termination: i = -1 (out of bounds), loop exits

Result: Total negative count = 4

The path we traced was: [2,0] → [2,1] → [1,1] → [1,2] → [0,2], efficiently finding all 4 negative numbers (-1, -3, -2, -1) by following the boundary between non-negative and negative regions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the number of rows and n is the number of columns in the grid.

The algorithm starts from the bottom-left corner of the grid (position [m-1, 0]) and traverses in a staircase pattern. In each iteration, it either moves up one row (i -= 1) or moves right one column (j += 1). Since i starts at m-1 and can only decrease to 0 (maximum m moves up), and j starts at 0 and can only increase to n-1 (maximum n moves right), the total number of iterations is at most m + n. Each iteration performs constant time operations, resulting in O(m + n) time complexity.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables m, n, i, j, and ans, regardless of the input size. No additional data structures are created that scale with the input dimensions.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Starting from the Wrong Corner

Pitfall: A common mistake is starting from the top-left corner [0, 0] or bottom-right corner [m-1, n-1]. These positions don't provide an efficient traversal path because you can't make definitive decisions about which direction to move.

Why it fails:

• From top-left [0, 0]: When you encounter a negative, you can't determine if there are more negatives to the left or above.
• From bottom-right [m-1, n-1]: When you encounter a non-negative, you can't efficiently determine where the boundary is.

Solution: Always start from either bottom-left [m-1, 0] or top-right [0, n-1] corners. These positions allow for a clear decision path:

# Correct: Starting from bottom-left
row_idx, col_idx = rows - 1, 0

# Alternative correct approach: Starting from top-right
# row_idx, col_idx = 0, cols - 1
# (would require adjusting the traversal logic accordingly)

2. Incorrect Boundary Checking

Pitfall: Using wrong boundary conditions in the while loop, such as while row_idx > 0 and col_idx < cols - 1 or forgetting to check boundaries altogether.

Why it fails: This would miss processing the first row (index 0) or the last column, potentially missing negative numbers in these positions.

Solution: Ensure the loop continues while the indices are within valid bounds:

# Correct boundary check
while row_idx >= 0 and col_idx < cols:
    # Process current position

3. Double Counting or Missing Elements

Pitfall: When finding a negative number, incorrectly calculating the count by using cols - col_idx - 1 or cols - col_idx + 1 instead of cols - col_idx.

Why it fails:

• Using cols - col_idx - 1 would not count the current negative element itself
• Using cols - col_idx + 1 would count one extra non-existent element

Solution: Remember that when at column index col_idx, there are exactly cols - col_idx elements from this position to the end of the row (inclusive):

if grid[row_idx][col_idx] < 0:
    # Correct: counts current element and all elements to its right
    negative_count += cols - col_idx
    row_idx -= 1

4. Incorrect Movement Direction

Pitfall: Moving in the wrong direction after finding a negative or non-negative number, such as moving down instead of up when a negative is found.

Why it fails: This breaks the algorithm's invariant and may lead to revisiting cells or missing negatives entirely.

Solution: Follow the correct movement pattern:

if grid[row_idx][col_idx] < 0:
    # Found negative: move UP (we've counted this row's negatives)
    row_idx -= 1
else:
    # Found non-negative: move RIGHT (looking for negatives in this row)
    col_idx += 1

5. Handling Edge Cases

Pitfall: Not considering edge cases like empty grids, single-row, or single-column matrices.

Why it fails: The code might crash or return incorrect results for these special cases.

Solution: While the provided code handles these cases naturally, it's good practice to explicitly verify:

# The algorithm naturally handles edge cases:
# - Empty grid: would have rows=0 or cols=0, loop never executes
# - Single row: row_idx starts at 0, processes correctly
# - Single column: col_idx can only be 0, processes correctly
# - All negative: counts all elements correctly
# - All non-negative: returns 0 correctly