1351. Count Negative Numbers in a Sorted Matrix
Problem Description
Given a matrix grid
which has dimensions m x n
, our task is to count all the negative numbers within this grid. The matrix is sorted in a non-increasing (also known as non-decreasing) order across both rows and columnsāthis means the numbers go from larger on the top-left to smaller on the bottom-right.
To visualize, we might have a matrix like this:
4 3 2 -1 3 2 1 -1 1 1 -1 -2 -1 -1 -2 -3
In the above example, you can see that rows and columns are sorted in non-increasing order and there are 8 negative numbers.
The goal is to count how many negative numbers are present.
Intuition
Since the grid is sorted in non-increasing order row-wise and column-wise, we can use a more efficient approach than checking each cell individually.
Here's the intuition step by step:
-
We start at the bottom-left corner of the matrix (
grid[m - 1][0]
). The reason for doing this is that if this number is negative, then all numbers to its right are guaranteed to be negative because the row is sorted in non-increasing order. On the other hand, if this number is not negative, we can move one column to the right. -
We keep track of our current position with indices
i
for rows andj
for columns. We setans
to 0 to keep track of our count of negative numbers. -
We use a while loop that runs as long as
i
is within the rows andj
is within the columns of the grid. -
If the current element where we are (
grid[i][j]
) is negative, we add the count of remaining columns in that row to our answer (i.e.,ans += n - j
) because all of these will be negative. After doing that, we move one row up (i -= 1
) since we're done with the current row. -
If the element is not negative, we move one column to the right (
j += 1
) to check the next number in the same row. -
The process is repeated until we've gone through all rows or columns.
-
We return the count
ans
which contains the number of negative numbers in the grid at the end of our loop.
The solution leverages the sorted property of the matrix to skip over non-negative elements and only count consecutive negatives, which makes it efficient.
Learn more about Binary Search patterns.
Solution Approach
The solution uses a simple algorithm that takes advantage of the properties of the matrix, namely that it is sorted in non-increasing order in both rows and columns. No additional data structures are needed; we can operate directly on the given grid
.
Here is a step-by-step walkthrough of the implementation:
-
Initiate two pointers,
i
for rows, starting from the last row (m - 1
), andj
for columns, starting from the first column (0
). -
Initiate a variable
ans
to store the count of negative numbers, initially set to 0. -
Enter a while loop with the condition that
i
is greater than or equal to 0 (to make sure we are within the bounds of the rows) andj
is less thann
(to make sure we are within the bounds of the columns). -
In the loop, check if the current element
grid[i][j]
is negative. If it is, incrementans
by the number of columns remaining in the current row (n - j
). This is because, since the rows are non-increasing, all elements to the right ofgrid[i][j]
will also be negative. Then, decrease the row pointeri
by 1, to move up to the previous row. -
If
grid[i][j]
is not negative, just move to the next column by incrementingj
by 1. -
The loop continues until one of the exit conditions of the while loop is met (either all rows have been checked or the end of a row has been reached).
-
Finally, return the
ans
variable, which now contains the count of negative numbers in the grid.
The time complexity of this algorithm is O(m + n), where m is the number of rows and n is the number of columns. This is because at each step of the algorithm, we're either moving one row up or one column to the right until we exit the matrix bounds. In the worst-case scenario, we'll make m+n moves.
The space complexity is O(1) as we are not using any additional space proportional to the size of the input grid; instead, we're just using a few extra variables for counting and indexing.
No complex patterns are used here; the implementation is straightforward once the insight about the grid's sorted property is understood.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a smaller example to clearly illustrate the use of the solution approach in a concrete situation. Suppose we have the following grid
matrix with dimensions 3 x 4
:
3 2 1 -1 2 1 -1 -2 1 -1 -2 -3
We want to count the number of negative numbers in this grid. Here's how we can apply the solution approach:
-
We initialize our pointers
i
with the index of the last row which is2
for this grid (since we are using 0-based indexing), andj
with the index of the first column which is0
. -
We set
ans
to0
as our count of negative numbers. -
We begin our while loop. Our initial element to check is
grid[2][0]
, which is1
. Since it's not negative, we move one column to the right by incrementingj
to1
. -
Now,
grid[2][1]
is-1
, which is negative. We find that there are4 - 1 = 3
columns remaining in the row, including the current column. So, we add3
toans
, making it3
, and move up a row by decrementingi
to1
. -
Our new position is
grid[1][1]
, which is1
. It's not negative, so we move one column to the right again by incrementingj
to2
. -
We check
grid[1][2]
, it's-1
. There are4 - 2 = 2
columns remaining, so we add2
toans
, which becomes5
. We then move up a row by decrementingi
to0
. -
The element
grid[0][2]
is1
, not negative. We incrementj
to3
. -
At
grid[0][3]
, we have-1
. With only1
column at this last index, we add1
toans
, resulting in a final count of6
. Since there are no more rows above, the loop ends here asi
is decremented and falls below0
.
Thus, the grid
contains 6
negative numbers.
With this example, it is clear how the algorithm smartly traverses the matrix, leveraging the sorted property to count negative numbers efficiently, without needing to check each element.
Solution Implementation
1class Solution:
2 def countNegatives(self, grid: List[List[int]]) -> int:
3 # Get the dimensions of the grid
4 num_rows, num_cols = len(grid), len(grid[0])
5
6 # Initialize pointers for the row and column
7 row_index, col_index = num_rows - 1, 0
8
9 # Initialize counter for negative numbers
10 negative_count = 0
11
12 # Iterate over the grid, starting from the bottom left corner
13 while row_index >= 0 and col_index < num_cols:
14 # If current element is negative
15 if grid[row_index][col_index] < 0:
16 # All elements in the current row to the right are also negative
17 negative_count += num_cols - col_index
18
19 # Move up to the previous row
20 row_index -= 1
21 else:
22 # Move right to the next column
23 col_index += 1
24
25 # Return the total count of negative numbers
26 return negative_count
27
1class Solution {
2 public int countNegatives(int[][] grid) {
3 int rowCount = grid.length; // The number of rows in the grid.
4 int colCount = grid[0].length; // The number of columns in the grid.
5 int negativeCount = 0; // Initialize a count for negative numbers.
6
7 // Start from the bottom-left corner of the grid and move upwards in rows and rightwards in columns.
8 for (int rowNum = rowCount - 1, colNum = 0; rowNum >= 0 && colNum < colCount;) {
9 // If the current element is negative, all the elements to its right are also negative.
10 if (grid[rowNum][colNum] < 0) {
11 negativeCount += colCount - colNum; // Add the remaining elements in the row to the count.
12 rowNum--; // Move up to the previous row to continue checking for negatives.
13 } else {
14 colNum++; // Move right to the next column to check for non-negative elements.
15 }
16 }
17
18 return negativeCount; // Return the total count of negative numbers in the grid.
19 }
20}
21
1#include <vector> // Necessary for using vectors
2
3class Solution {
4public:
5 // Function to count the number of negative numbers in a 2D grid
6 int countNegatives(std::vector<std::vector<int>>& grid) {
7 int rowCount = grid.size(); // Number of rows in the grid
8 int colCount = grid[0].size(); // Number of columns in the grid
9 int negativeCount = 0; // Initialize the counter for negative numbers
10
11 // Start from the bottom-left corner of the grid
12 int currentRow = rowCount - 1;
13 int currentColumn = 0;
14
15 // Loop through the grid diagonally
16 while (currentRow >= 0 && currentColumn < colCount) {
17 // If the current element is negative, then all elements to its right are also negative
18 if (grid[currentRow][currentColumn] < 0) {
19 negativeCount += colCount - currentColumn; // Add all negative numbers in the current row
20 --currentRow; // Move up to the previous row to continue with the negative number sweep
21 } else {
22 // If the current element is not negative, move right to the next column
23 ++currentColumn;
24 }
25 }
26
27 // Return the total count of negative numbers found in the grid
28 return negativeCount;
29 }
30};
31
1// Counts the number of negative numbers in a row-wise and column-wise sorted grid.
2// @param grid - A 2D array of numbers where each row and column is sorted in non-increasing order.
3// @returns The total count of negative numbers in the grid.
4function countNegatives(grid: number[][]): number {
5 // Number of rows in the grid
6 const rowCount = grid.length;
7 // Number of columns in the grid - assumes at least 1 row exists
8 const columnCount = grid[0].length;
9 // Counter for negative numbers
10 let negativeCount = 0;
11
12 // Start from the bottom-left corner of the grid
13 let row = rowCount - 1;
14 let column = 0;
15
16 // Loop until we reach the top of the grid or the end of a row
17 while (row >= 0 && column < columnCount) {
18 // If the current number is negative,
19 // add all remaining negatives in the row to the counter
20 // (as the row is sorted in non-increasing order)
21 if (grid[row][column] < 0) {
22 // All numbers to the right of the current position are negative
23 negativeCount += columnCount - column;
24 // Move up to the previous row since we've counted all negatives in the current row
25 row--;
26 } else {
27 // If the current number is non-negative, move right to the next column
28 column++;
29 }
30 }
31
32 // Return total count of negative numbers
33 return negativeCount;
34}
35
Time and Space Complexity
The provided code implements an algorithm to count the number of negative numbers in an m x n
grid, which is assumed to be non-increasing both row-wise and column-wise. The algorithm starts from the bottom-left corner of the grid and moves upwards or to the right depending on the sign of the current cell value.
Time Complexity:
The time complexity of the code can be analyzed as follows:
- The outer loop runs a maximum of
m
times if we're moving upwards from the bottom row to the topmost row in the worst case. - The inner condition can lead to moving rightwards across up to
n
columns.
However, you will never revisit a row or a column once you've moved on from it (since you move up if you find a negative and move right if you find a non-negative number), meaning each cell is visited at most once. Therefore, the maximum number of steps is m + n
.
Thus, the time complexity of the algorithm is O(m + n)
.
Space Complexity:
The space complexity of the code is:
- Constant extra space is used for the variables
m
,n
,i
,j
, andans
. - No additional data structures are being used that grow with the size of the input.
Considering the above points, the overall space complexity of the algorithm is O(1)
, as it uses a constant amount of extra space regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!