algoadvance

Leetcode 1351. Count Negative Numbers in a Sorted Matrix

Problem Statement

You are given an m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, meaning both grid[i] and grid[j][i] are sorted in non-increasing order. Return the number of negative numbers in grid.

Example 1:

Input:

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

Output:

8

Example 2:

Input:

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

Output:

0

Clarifying Questions

1. Q: Can the matrix contain positive numbers as well as zeroes? A: Yes, the matrix can contain positive numbers and zeroes.

2. Q: Is there a specific data type expected for the output? A: The output should be an integer representing the count of negative numbers.

3. Q: Are the dimensions (m and n) of the grid always positive integers? A: Yes, the dimensions of the grid are always positive integers greater than 0.

Strategy

The matrix is sorted in non-increasing order both row-wise and column-wise. This property allows us to use a more efficient approach than checking each element one by one.

Optimized Approach:

1. Start from the top-right corner of the matrix.
2. If the current element is negative, it means all elements below this element in the same column are also negative (because the column is sorted in non-increasing order). So, move down and count all such elements.
3. If the current element is non-negative, move left to the next column.
4. Continue this process until you traverse the entire matrix.

Steps:

1. Initialize a counter to keep track of negative numbers.
2. Initialize position to the top-right of the grid grid[0][n-1].
3. Use two pointers approach:
   • One pointer i for rows, starting at 0.
   • One pointer j for columns, starting at n-1.
4. Traverse the grid using the pointers:
   • While i is within the range of rows and j within the range of columns:
     • If grid[i][j] is negative, add (m - i) (remaining elements in this column) to the counter and move left (j--).
     • If grid[i][j] is not negative, move down (i++).

Code

public class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        
        int i = 0, j = n - 1;
        
        while (i < m && j >= 0) {
            if (grid[i][j] < 0) {
                // All elements below grid[i][j] in the same column are negative
                count += (m - i);
                j--;
            } else {
                i++;
            }
        }
        
        return count;
    }
}

Time Complexity

• Time Complexity: O(m + n)
  • We traverse at most m rows and n columns. Each step either moves to the next row or the previous column.
• Space Complexity: O(1)
  • We use only a constant amount of space for variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?