Jobs

Interviews

Discussions

Count Negative Numbers in a Sorted Matrix

Easy

Google

2 views

Topics:

ArraysBinary Search

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 grid.

For example, consider this grid:

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

In this example, the correct output is 8 because there are 8 negative numbers in the matrix.

As another example, consider this grid:

[
  [3, 2],
  [1, 0]
]

In this example, the correct output is 0 because there are no negative numbers in the matrix.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Could you find an O(n + m) solution?

Count Negative Numbers in a Sorted Matrix

Easy

Google

2 views

Topics:

ArraysBinary Search

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 grid.

For example, consider this grid:

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

In this example, the correct output is 8 because there are 8 negative numbers in the matrix.

As another example, consider this grid:

[
  [3, 2],
  [1, 0]
]

In this example, the correct output is 0 because there are no negative numbers in the matrix.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Could you find an O(n + m) solution?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix grid, and what is the maximum size for the rows and columns?
What is the range of integer values within the grid? Are extremely large negative numbers possible?
Is it possible for the input grid to be null or empty (zero rows or zero columns)?
Is the matrix guaranteed to be rectangular (i.e., each row has the same number of columns)?
If a row contains both positive and negative numbers, where will the transition occur due to the non-increasing order (all negative numbers before positive numbers, or vice-versa)?

Brute Force Solution

Approach

The brute force method for this problem involves examining each number in the matrix one by one. The goal is simply to count how many of those numbers are negative. We don't use any of the sorted properties.

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the matrix.
Check if that number is negative.
If it is, add one to our running total of negative numbers.
Now, move on to the next number in the matrix, going row by row.
Repeat the checking process for each number: see if it's negative, and if so, increase the total.
Continue until you've looked at every single number in the entire matrix.
The final total will be the count of all the negative numbers.

Code Implementation

def count_negatives_brute_force(matrix): 
    negative_count = 0
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0

    # Iterate through each row of the matrix
    for row_index in range(number_of_rows):

        # Iterate through each column of the current row
        for column_index in range(number_of_columns):
            current_number = matrix[row_index][column_index]

            # Check if the current number is negative
            if current_number < 0:

                # Increment the negative count since we found a negative number
                negative_count += 1

    return negative_count

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each element of the matrix. The matrix has 'm' rows and 'n' columns. For each element, a constant-time comparison is performed to check if it is negative. Therefore, the algorithm performs a constant operation m * n times, resulting in a time complexity of O(m*n). If m and n were always equivalent, this could also be written as O(n²).

Space Complexity

O(1) – The provided algorithm initializes a single integer variable to track the running total of negative numbers. No additional data structures like arrays, lists, or hash maps are created. The space required for this counter variable is independent of the matrix dimensions (number of rows and columns). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The straightforward way to count negative numbers is too slow. We can do better by starting in a special corner of the matrix and using the sorted nature of the data to quickly eliminate large portions of the matrix from consideration.

Here's how the algorithm would work step-by-step:

Start at the top right corner of the matrix.
Check if the current number is negative.
If it is negative, then all numbers below it in the same column are also negative. So, increase the count by the number of rows below the current number (including the current row), and move to the column on the left.
If it is not negative, then all numbers to the left of it in the same row are also non-negative. So, move to the row below.
Repeat steps 2-4 until you reach the end of the matrix.

Code Implementation

def count_negatives(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    current_row = 0
    current_column = number_of_columns - 1
    negative_count = 0

    while current_row < number_of_rows and current_column >= 0:
        # Starting from top-right, check the current element
        if grid[current_row][current_column] < 0:
            # All elements below are negative
            negative_count += number_of_rows - current_row

            current_column -= 1

        else:
            # Move to the next row if the element is non-negative
            current_row += 1

    return negative_count

Big(O) Analysis

Time Complexity

O(m + n) – The algorithm starts at the top right corner of the m x n matrix and either moves one column to the left or one row down in each step. In the worst-case scenario, it might traverse all the columns (n columns) or all the rows (m rows). Thus, the number of operations will be proportional to m + n. Hence, the time complexity is O(m + n), where m is the number of rows and n is the number of columns.

Space Complexity

O(1) – The provided algorithm operates in place without using any auxiliary data structures like lists, dictionaries, or sets. It only utilizes a few integer variables (row index, column index, and count) to traverse the matrix and store the running count of negative numbers. The space used by these variables remains constant regardless of the size of the input matrix (number of rows and columns). Therefore, the auxiliary space complexity is O(1), indicating constant space.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0, as there are no numbers to count in an empty grid.
Grid with zero rows or zero columns	Return 0, as an effectively empty grid contains no negative numbers.
Grid with a single row containing only positive numbers	Return 0, as no negative numbers are present to count.
Grid with a single row containing only negative numbers	Return the number of columns, as all numbers are negative.
Grid with all elements as zero	Return 0, as zero is not a negative number.
Grid with all elements as the smallest possible integer	Return rows * cols, as all elements will be negative.
Grid with dimensions close to integer limits (large row/col count)	Ensure the counting algorithm doesn't cause integer overflow, particularly if multiplying row/col counts.
Grid with a mix of very large positive numbers and very small negative numbers	Standard comparison operators should handle both extremes correctly without special handling.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix grid, and what is the maximum size for the rows and columns?
What is the range of integer values within the grid? Are extremely large negative numbers possible?
Is it possible for the input grid to be null or empty (zero rows or zero columns)?
Is the matrix guaranteed to be rectangular (i.e., each row has the same number of columns)?
If a row contains both positive and negative numbers, where will the transition occur due to the non-increasing order (all negative numbers before positive numbers, or vice-versa)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the matrix.
Check if that number is negative.
If it is, add one to our running total of negative numbers.
Now, move on to the next number in the matrix, going row by row.
Repeat the checking process for each number: see if it's negative, and if so, increase the total.
Continue until you've looked at every single number in the entire matrix.
The final total will be the count of all the negative numbers.

Code Implementation

def count_negatives_brute_force(matrix): 
    negative_count = 0
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0

    # Iterate through each row of the matrix
    for row_index in range(number_of_rows):

        # Iterate through each column of the current row
        for column_index in range(number_of_columns):
            current_number = matrix[row_index][column_index]

            # Check if the current number is negative
            if current_number < 0:

                # Increment the negative count since we found a negative number
                negative_count += 1

    return negative_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top right corner of the matrix.
Check if the current number is negative.
If it is negative, then all numbers below it in the same column are also negative. So, increase the count by the number of rows below the current number (including the current row), and move to the column on the left.
If it is not negative, then all numbers to the left of it in the same row are also non-negative. So, move to the row below.
Repeat steps 2-4 until you reach the end of the matrix.

Code Implementation

def count_negatives(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    current_row = 0
    current_column = number_of_columns - 1
    negative_count = 0

    while current_row < number_of_rows and current_column >= 0:
        # Starting from top-right, check the current element
        if grid[current_row][current_column] < 0:
            # All elements below are negative
            negative_count += number_of_rows - current_row

            current_column -= 1

        else:
            # Move to the next row if the element is non-negative
            current_row += 1

    return negative_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0, as there are no numbers to count in an empty grid.
Grid with zero rows or zero columns	Return 0, as an effectively empty grid contains no negative numbers.
Grid with a single row containing only positive numbers	Return 0, as no negative numbers are present to count.
Grid with a single row containing only negative numbers	Return the number of columns, as all numbers are negative.
Grid with all elements as zero	Return 0, as zero is not a negative number.
Grid with all elements as the smallest possible integer	Return rows * cols, as all elements will be negative.
Grid with dimensions close to integer limits (large row/col count)	Ensure the counting algorithm doesn't cause integer overflow, particularly if multiplying row/col counts.
Grid with a mix of very large positive numbers and very small negative numbers	Standard comparison operators should handle both extremes correctly without special handling.