algoadvance

Leetcode 1351. Count Negative Numbers in a Sorted Matrix

Problem Statement

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in the matrix.

Clarifying Questions

Before we jump into coding, let’s clarify a few things about the problem statement:

  1. Can grid contain zeros and positive values?
    Yes, the problem statement allows any integer values as long as the matrix is sorted in non-increasing order both row-wise and column-wise.
  2. What should be returned if there are no negative numbers?
    The function should return 0.
  3. Are there any limitations on the size of the matrix (m and n)?
    The matrix dimensions are not specified in the problem statement, but typical constraints apply such as reasonable limits for a coding interview setting.

Strategy

A brute force method would be to iterate over every element in the matrix to count the negative numbers. However, since the matrix is sorted in non-increasing order, we can take advantage of this property to come up with a more efficient approach.

Here’s a more optimal strategy we can use:

  1. Start from the top-right corner of the matrix.
  2. If the current element is negative, all elements below it in the same column are also negative (because the column is non-increasing). So, count all these negative numbers and move to the left.
  3. If the current element is non-negative, move downwards as all elements to its left are larger or equal to the current element (and hence non-negative).

This way, we minimize the number of elements we need to check, leading to a more efficient solution.

Code

Here’s the implementation of the described strategy in C++:

#include <vector>

class Solution {
public:
    int countNegatives(std::vector<std::vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int count = 0;

        int row = 0, col = n - 1;  // Start from the top-right corner of the matrix
        
        while(row < m && col >= 0) {
            if(grid[row][col] < 0) {
                // If grid[row][col] is negative, all elements below in the same column are negative.
                count += (m - row);
                col--;  // Move left
            } else {
                // Move down.
                row++;
            }
        }

        return count;
    }
};

Time Complexity

The time complexity of this approach is O(m + n), where m is the number of rows and n is the number of columns in the matrix. This is because, in the worst case, we might need to traverse each row and each column at most once. Hence, this solution is much more efficient than the brute-force approach which would have a time complexity of O(m * n).

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