Count Negative Numbers in Sorted Matrix

📋

Problem

Imagine you are analyzing temperature data from a grid of sensors, and you want to quickly count how many sensors recorded below-freezing temperatures.

Given an m x n matrix sorted in non-increasing order both row-wise and column-wise (each row and column is sorted in decreasing order), count the number of negative numbers in the matrix. Input: a 2D integer matrix. Output: an integer representing the count of negative numbers.

1 ≤ m, n ≤ 1000-10^5 ≤ matrix[i][j] ≤ 10^5Rows and columns are sorted in non-increasing order

Edge cases: Matrix with all positive numbers → output 0Matrix with all negative numbers → output m*nMatrix with a single element negative → output 1

</>

IDE

def countNegatives(grid: list[list[int]]) -> int:public int countNegatives(int[][] grid)int countNegatives(vector<vector<int>>& grid)function countNegatives(grid)

def countNegatives(grid):
    # Write your solution here
    pass

class Solution {
    public int countNegatives(int[][] grid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countNegatives(vector<vector<int>>& grid) {
    // Write your solution here
    return 0;
}

function countNegatives(grid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Failing to count any negatives due to incorrect sign check or skipping negative elements.✅ Use condition 'num < 0' to count negatives and iterate all elements or use staircase search.

Wrong: m*nCounting all elements as negative without checking sign properly.✅ Check each element's sign before counting; only count if less than zero.

Wrong: Incorrect count due to greedy row-wise countingAssuming negatives only appear at row ends without considering column order.✅ Implement staircase search from top-right corner to count negatives correctly.

Wrong: Counting zeros as negativeUsing condition 'num <= 0' instead of 'num < 0'.✅ Change condition to strictly 'num < 0' to exclude zeros.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Think about common algorithmic pitfalls like greedy traps and boundary conditions.

Optimize your solution to avoid brute force time complexity.

t1_01basic

Input{"grid":[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]}

Expected8

⏱ Performance - must finish in 2000ms

There are 8 negative numbers in the matrix: -1, -1, -1, -2, -1, -1, -2, -3.

💡 Consider scanning from the top-right corner to count negatives efficiently.

💡 Use the staircase search approach to move left or down based on sign.

💡 If current element is negative, all elements below in that column are negative; count them and move left.

Why it failed: Incorrect count likely due to not leveraging sorted order; fix by implementing staircase search from top-right corner.

✓ Correctly counts negatives using the staircase search approach.

t1_02basic

Input{"grid":[[5,3,0,-1],[4,2,-1,-2],[3,1,-2,-3]]}

Expected5

⏱ Performance - must finish in 2000ms

Negative numbers are -1, -1, -2, -2, -3 totaling 5 negatives.

💡 Try binary searching each row for the first negative number.

💡 Since rows are sorted decreasingly, find the first index where element < 0.

💡 Sum counts of negatives from each row starting at that index.

Why it failed: Counting all negatives without using sorted property causes inefficiency; fix by binary searching each row for first negative.

✓ Correctly counts negatives using binary search per row.

t2_01edge

Input{"grid":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty matrix has no elements, so zero negatives.

💡 Check if the input matrix is empty before processing.

💡 Return 0 immediately if there are no rows.

💡 Avoid index errors by handling empty input explicitly.

Why it failed: Code crashes or returns non-zero on empty input; fix by adding a check for empty matrix and returning 0.

✓ Handles empty matrix input correctly by returning 0.

t2_02edge

Input{"grid":[[-5]]}

Expected1

⏱ Performance - must finish in 2000ms

Single element matrix with negative number counts as 1 negative.

💡 Test single element matrices to ensure base case correctness.

💡 Check if the single element is negative and count accordingly.

💡 Return 1 if negative, else 0.

Why it failed: Fails to count single negative element; fix by correctly handling single-element matrices.

✓ Correctly counts single negative element.

t2_03edge

Input{"grid":[[5]]}

Expected0

⏱ Performance - must finish in 2000ms

Single element matrix with non-negative number counts as 0 negatives.

💡 Test single element matrices with non-negative values.

💡 Return 0 if element is zero or positive.

💡 Ensure no false positives in counting negatives.

Why it failed: Incorrectly counts non-negative single element as negative; fix by checking element sign precisely.

✓ Correctly returns 0 for single non-negative element.

t3_01corner

Input{"grid":[[10,5,0],[9,4,-1],[8,3,-2]]}

Expected2

⏱ Performance - must finish in 2000ms

Negative numbers are -1 and -2 only, total 2 negatives.

💡 Beware of greedy approaches that count negatives row-wise without considering column order.

💡 Use staircase search to avoid missing negatives in columns.

💡 Move left when negative found, down when non-negative found.

Why it failed: Greedy row-wise counting misses negatives in columns; fix by implementing staircase search from top-right corner.

✓ Correctly counts negatives using staircase search avoiding greedy trap.

t3_02corner

Input{"grid":[[3,2,1],[2,1,0],[1,0,-1]]}

Expected1

⏱ Performance - must finish in 2000ms

Only one negative number: -1 at bottom-right corner.

💡 Check if your solution confuses 0/1 knapsack style counting with this problem.

💡 Ensure counting is based on sign, not presence or absence of elements.

💡 Use binary search or staircase search to find first negative per row.

Why it failed: Confusing problem with knapsack leads to incorrect counting; fix by focusing on sign checks and sorted order.

✓ Correctly counts negatives by sign and sorted order.

t3_03corner

Input{"grid":[[0,0,0],[0,0,0],[0,0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

All zeros are non-negative, so count is zero.

💡 Check if your code treats zero as negative incorrectly.

💡 Ensure condition is strictly less than zero for negatives.

💡 Test boundary values like zero carefully.

Why it failed: Counting zeros as negative due to incorrect condition; fix by using 'num < 0' strictly.

✓ Correctly excludes zeros from negative count.

t4_01performance

Input{"_description":"n=1000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size m=n=1000, O(m+n) or O(m log n) solution must complete within 2 seconds.

💡 Brute force O(m*n) may be too slow for large inputs.

💡 Use staircase search O(m+n) or binary search O(m log n) for efficiency.

💡 Avoid nested loops over entire matrix.

Why it failed: TLE due to O(m*n) brute force; fix by implementing O(m+n) staircase search or O(m log n) binary search per row.

✓ Efficient solution runs within time limit using optimal search approach.

Practice

1. You are given a matrix of integers. You need to find all elements that are the smallest in their row and simultaneously the largest in their column. Which approach guarantees an optimal solution to this problem?

easy

A. Use a brute force approach checking each element by scanning its entire row and column repeatedly.

B. Precompute the minimum value of each row and the maximum value of each column, then find elements matching both conditions in a single pass.

C. Apply a dynamic programming approach to store intermediate minimum and maximum values for submatrices.

D. Use a greedy approach by selecting the smallest element in each row and checking if it is the largest in its column.

Solution

1. Step 1: Understand problem constraints

   The problem requires identifying elements that are simultaneously the minimum in their row and maximum in their column.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but inefficient. DP (C) is unnecessary overhead. Greedy (D) can fail if multiple minimums exist in a row but only one is maximum in its column. Precomputing row minimums and column maximums (B) allows a single pass to find all lucky numbers efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Precompute arrays then single pass -> optimal and correct [OK]

Hint: Precompute mins and maxes for single pass [OK]

Common Mistakes:

• Assuming greedy selection per row suffices
• Using DP unnecessarily
• Brute force is too slow

2. Consider this buggy code snippet for diagonal traversal. Which line contains the subtle bug that causes incorrect traversal or index errors?

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        r_start = max(0, d - n + 1)
        r_end = min(d, m - 1)
        if d % 2 == 0:
            for r in range(r_start, r_end + 1):  # Bug here: direction wrong
                c = d - r
                result.append(mat[r][c])
        else:
            for r in range(r_end, r_start - 1, -1):
                c = d - r
                result.append(mat[r][c])
    return result

medium

A. Line with 'r_start = max(0, d - n + 1)'

B. Line with 'for r in range(r_start, r_end + 1):' inside even diagonal block

C. Line with 'c = d - r' inside loops

D. Line with 'for d in range(m + n - 1):'

Solution

1. Step 1: Identify traversal direction for even diagonals

   Even diagonals must traverse from r_end down to r_start (descending).

2. Step 2: Check loop direction in buggy code

   The loop uses ascending range from r_start to r_end, which is incorrect and causes wrong order or index errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing loop direction restores correct traversal [OK]

Hint: Even diagonals traverse downward (descending indices) [OK]

Common Mistakes:

• Using ascending loop for even diagonals causing order errors

3. What is the time and space complexity of the optimal in-place Set Matrix Zeroes algorithm that uses the first row and column as flags for an m x n matrix?

medium

A. Time: O(m * n), Space: O(1)

B. Time: O(m * n), Space: O(m + n)

C. Time: O(m + n), Space: O(1)

D. Time: O(m * n * (m + n)), Space: O(1)

Solution

1. Step 1: Identify loops

   The algorithm iterates over the entire matrix multiple times, each pass O(m*n).

2. Step 2: Analyze space usage

   Only constant extra variables and flags in first row/column are used, so O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two nested loops over matrix -> O(m*n) time; no extra arrays -> O(1) space [OK]

Hint: Nested loops over matrix -> O(m*n) time [OK]

Common Mistakes:

• Confusing space for flag arrays as O(m+n) instead of O(1)
• Assuming single pass -> O(m+n) time
• Overestimating time as O(m*n*(m+n)) due to nested loops

4. What is the time complexity of the optimal in-place boundary shrinking approach to generate an n x n spiral matrix, and why?

medium

A. O(n²) because every cell in the matrix is visited exactly once

B. O(n) because each boundary shrinks linearly

C. O(n³) due to nested loops and repeated boundary checks

D. O(n log n) because of direction cycling and boundary updates

Solution

1. Step 1: Identify the number of cells to fill

   The matrix has n² cells, each must be assigned a value exactly once.

2. Step 2: Analyze loops and operations

   Each iteration fills one side of the current boundary, and boundaries shrink inward. The total number of assignments sums to n², so time complexity is O(n²).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Every cell visited once -> O(n²) time [OK]

Hint: Each cell visited once -> O(n²) time [OK]

Common Mistakes:

• Confusing boundary shrinking with linear time
• Assuming nested loops multiply to cubic time
• Ignoring that direction cycling is constant time

5. Suppose the Game of Life rules are modified so that cells can be in one of three states: dead, alive, or dormant, and the next state depends on neighbors' states with more complex transitions. Which modification to the in-place encoding approach is necessary to correctly update the board?

hard

A. Use a larger integer encoding scheme with more states to represent current and next states simultaneously.

B. Switch to copying the entire board each iteration to avoid encoding complexity.

C. Update cells immediately without encoding since more states simplify neighbor counting.

D. Ignore dormant state neighbors during counting to reduce complexity.

Solution

1. Step 1: Understand the need for more states

   With three possible states and complex transitions, encoding must represent both current and next states simultaneously.

2. Step 2: Choose encoding approach

   Using a larger integer encoding scheme (e.g., 6 or more states) allows in-place updates without losing original state info.

3. Step 3: Reject naive approaches

   Copying the board increases space; immediate updates corrupt neighbor info; ignoring dormant neighbors breaks rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   More states require richer encoding to preserve info [OK]

Hint: More states require more encoding bits, not naive copying [OK]

Common Mistakes:

• Switching to copying board wastes space
• Immediate updates corrupt neighbor counts
• Ignoring certain neighbors breaks rules