algoadvance

You’re given an m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Your task is to count the number of negative numbers in the grid.

Example:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8

Clarifying Questions

1. What should be the behavior for empty grids?
   • If the grid is empty, the output should be 0 as there are no elements to count.
2. Can grid contain zeros?
   • Yes, the grid can contain zeros or positive numbers too.
3. What is the maximum size of the grid?
   • This detail isn’t provided in the problem statement, but typical constraints for LeetCode matrix problems involve grid dimensions in the range of 1 <= m, n <= 100.

Strategy

Since the grid is sorted in non-increasing order both row-wise and column-wise:

1. Start from the bottom-left corner of the matrix.
2. Move right if the current element is negative.
3. Move up if the current element is non-negative.
4. Keep a count of all negatives encountered.

This strategy takes advantage of the sorted nature to ensure every element less than a known negative value is also counted efficiently.

Code

def countNegatives(grid):
    m, n = len(grid), len(grid[0])
    count = 0
    row, col = m - 1, 0
    
    while row >= 0 and col < n:
        if grid[row][col] < 0:
            count += (n - col)  # all the elements to the right in this row are negative
            row -= 1  # move up to the previous row
        else:
            col += 1  # move right to the next column
        
    return count

Time Complexity

• Time Complexity: O(m + n) - In the worst case, we traverse each row and column at most once.
• Space Complexity: O(1) - We use only a few extra variables for counting and indexing.

This approach is efficient for large matrices because it leverages the sorting property to avoid unnecessary checks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?