Solution Approach

The implementation uses binary search on each row to find the first negative number, following the exact boundary-finding template.

Algorithm Steps:

1. Initialize variables:

   • rows, cols = len(grid), len(grid[0]) - Get matrix dimensions
   • totalCount = 0 - Counter for negative numbers

2. For each row, apply binary search:

   • Initialize: left = 0, right = cols - 1, firstTrueIndex = -1
   • Define feasible condition: grid[row][mid] < 0 (is this position negative?)

3. Binary search loop (while left <= right):

   • Calculate mid = (left + right) // 2
   • If grid[row][mid] < 0: Found a negative (feasible is true)
     • Record this position: firstTrueIndex = mid
     • Search left for earlier negative: right = mid - 1
   • Else: Current element is non-negative
     • Search right for negatives: left = mid + 1

4. Count negatives for this row:

   • If firstTrueIndex != -1: Add cols - firstTrueIndex to total count
   • If firstTrueIndex == -1: No negatives in this row, add 0

5. Return the total count after processing all rows

Why this works:

Each row is sorted in non-increasing order, creating the pattern [non-neg, non-neg, ..., neg, neg]. Binary search finds the boundary (first negative) in O(log n) time. Once we know where negatives start, we count all remaining elements in that row.

Time Complexity: O(m log n) - Binary search O(log n) on each of m rows

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

Example Walkthrough

Let's trace through a small example using the binary search template:

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

Initial Setup:

• rows = 3, cols = 3 (3x3 matrix)
• totalCount = 0

Row 0: [3, 2, -1]

• Initialize: left = 0, right = 2, firstTrueIndex = -1
• Iteration 1: mid = 1, grid[0][1] = 2 ≥ 0 (not negative) → left = 2
• Iteration 2: mid = 2, grid[0][2] = -1 < 0 (negative!) → firstTrueIndex = 2, right = 1
• Loop ends: left = 2 > right = 1
• Result: firstTrueIndex = 2, add cols - 2 = 1 negative
• totalCount = 1

Row 1: [2, 0, -2]

• Initialize: left = 0, right = 2, firstTrueIndex = -1
• Iteration 1: mid = 1, grid[1][1] = 0 ≥ 0 (not negative) → left = 2
• Iteration 2: mid = 2, grid[1][2] = -2 < 0 (negative!) → firstTrueIndex = 2, right = 1
• Loop ends: left = 2 > right = 1
• Result: firstTrueIndex = 2, add cols - 2 = 1 negative
• totalCount = 2

Row 2: [1, -1, -3]

• Initialize: left = 0, right = 2, firstTrueIndex = -1
• Iteration 1: mid = 1, grid[2][1] = -1 < 0 (negative!) → firstTrueIndex = 1, right = 0
• Iteration 2: mid = 0, grid[2][0] = 1 ≥ 0 (not negative) → left = 1
• Loop ends: left = 1 > right = 0
• Result: firstTrueIndex = 1, add cols - 1 = 2 negatives
• totalCount = 4

Final Result: Total negative count = 4

The binary search found the first negative in each row: index 2, index 2, and index 1. By counting all elements from that index to the end of each row, we efficiently found all 4 negative numbers (-1, -2, -1, -3).

Time and Space Complexity

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

The algorithm performs binary search on each of the m rows. Each binary search takes O(log n) time since we're searching through n columns. Therefore, the total time is O(m × log n) = O(m log n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables like left, right, firstTrueIndex, and counters. 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. Using the Wrong Binary Search Template

Pitfall: Using while left < right with right = mid instead of the correct template with while left <= right and right = mid - 1.

Why it fails: Different binary search variants have different behaviors. Using the wrong template can cause off-by-one errors or infinite loops.

Solution: Always use the boundary-finding template with firstTrueIndex:

# Correct template
left, right = 0, cols - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if grid[row][mid] < 0:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

2. Returning left Instead of Tracking firstTrueIndex

Pitfall: Some solutions try to return left directly after the loop, which may point to an invalid index if no negative exists.

Why it fails: When there are no negatives in a row, left will equal cols (out of bounds), and using it directly would add incorrect counts.

Solution: Track firstTrueIndex explicitly and check if it's -1:

if first_true_index != -1:
    total_count += cols - first_true_index
# Otherwise, no negatives in this row, contribute 0

3. Incorrect Count Calculation

Pitfall: Counting cols - firstTrueIndex - 1 or cols - firstTrueIndex + 1 instead of cols - firstTrueIndex.

Why it fails:

• Using cols - firstTrueIndex - 1 would not count the first negative itself
• Using cols - firstTrueIndex + 1 would count an extra non-existent element

Solution: When firstTrueIndex is the index of the first negative, there are exactly cols - firstTrueIndex elements from that index to the end of the row (inclusive):

# If firstTrueIndex = 2 and cols = 5
# Elements at indices 2, 3, 4 are negative = 5 - 2 = 3 elements
total_count += cols - first_true_index

4. Not Resetting Variables for Each Row

Pitfall: Forgetting to reset left, right, and firstTrueIndex for each row's binary search.

Why it fails: Using stale values from the previous row's search will produce incorrect results.

Solution: Initialize all binary search variables inside the row loop:

for row in range(rows):
    left, right = 0, cols - 1  # Reset for each row
    first_true_index = -1       # Reset for each row
    # ... binary search ...

5. Handling Edge Cases

Pitfall: Not considering edge cases like all positive elements or all negative elements in a row.

Why it fails: The code might return incorrect counts.

Solution: The template handles these naturally:

# All positive row: firstTrueIndex stays -1, contributes 0
# All negative row: firstTrueIndex = 0, contributes cols - 0 = cols
# Single element row: binary search works correctly with left = right = 0