How do you solve Count Negative Numbers in a Sorted Matrix on LeetCode?

Count Negative Numbers in a Sorted Matrix (LeetCode #1351) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m) time complexity and O(1) space complexity. Key insight: The matrix is sorted in non-increasing order, allowing for efficient traversal.

What is the brute force solution for Count Negative Numbers in a Sorted Matrix?

The brute force approach for Count Negative Numbers in a Sorted Matrix is Brute Force, with O(m * n) time complexity and O(1) space complexity. The brute force approach involves iterating through every element in the matrix and counting how many of them are negative. This is straightforward but inefficient for larger matrices. The optimal Optimal Solution approach improves this to O(n + m).

What algorithm or data structure is used to solve Count Negative Numbers in a Sorted Matrix?

Count Negative Numbers in a Sorted Matrix uses the following concepts: Array, Binary Search, Matrix. The recommended patterns to study are: Two Pointers, Matrix Traversal.

What are the interview tips for Count Negative Numbers in a Sorted Matrix?

Always consider the properties of the input data; here, the sorted matrix is key. Explain your thought process clearly; it shows your understanding and can earn partial credit. Practice dry-running your solution on examples to ensure you understand the flow.

What are common mistakes when solving Count Negative Numbers in a Sorted Matrix?

Not recognizing the sorted nature of the matrix, leading to unnecessary iterations. Confusing the dimensions of the matrix when implementing the traversal logic.

#1351

Count Negative Numbers in a Sorted Matrix

Easy

ArrayBinary SearchMatrixTwo PointersMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n)	O(n + m)
Space	O(1)	O(1)

💡

Intuition

Time O(n + m)Space O(1)

The optimal approach leverages the sorted nature of the matrix. Starting from the top-right corner, we can move left if the current number is negative (to find more negatives) or down if it's non-negative. This way, we can count negatives in O(n + m) time.

⚙️

Algorithm

6 steps

1Step 1: Initialize a counter to zero.
2Step 2: Start from the top-right corner of the matrix (row 0, column n-1).
3Step 3: While within bounds, check the current element:
4Step 4: If the element is negative, increment the counter and move left (column--).
5Step 5: If the element is non-negative, move down (row++).
6Step 6: Continue until you move out of bounds.

solution.py13 lines

1# Full working Python code
2
3def countNegatives(grid):
4    count = 0
5    m, n = len(grid), len(grid[0])
6    row, col = 0, n - 1
7    while row < m and col >= 0:
8        if grid[row][col] < 0:
9            count += (m - row)
10            col -= 1
11        else:
12            row += 1
13    return count

ℹ

Complexity note: The time complexity is O(n + m) because in the worst case, we traverse either all rows or all columns. The space complexity is O(1) since we are using a constant amount of space for the counter and indices.

1The matrix is sorted in non-increasing order, allowing for efficient traversal.
2Counting negatives can be optimized by leveraging the sorted properties of the matrix.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.