Leetcode 1351: Count Negative Numbers in a Sorted Matrix
You are given an m x n matrix grid, sorted in non-increasing order both row-wise and column-wise. Your task is to determine how many negative numbers are present in the grid.
Problem
Approach
Steps
Complexity
Input: The input consists of a matrix grid where each row and each column is sorted in non-increasing order.
Example: For example, [[7,5,3,-1], [6,4,2,-1], [3,1,-2,-3], [-1,-2,-3,-4]].
Constraints:
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100
Output: The output should be an integer representing the count of negative numbers in the grid.
Example: For example, in the matrix [[7,5,3,-1], [6,4,2,-1], [3,1,-2,-3], [-1,-2,-3,-4]], the output would be 8.
Constraints:
• The result should be an integer representing the number of negative numbers.
Goal: To count the number of negative numbers in the grid by efficiently checking each row and column.
Steps:
• 1. Iterate through each row of the matrix.
• 2. For each row, use binary search or a direct check to count how many negative numbers are present.
• 3. Sum the results for each row to get the total count of negative numbers.
Goal: The matrix is sorted in non-increasing order both row-wise and column-wise.
Steps:
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100
Assumptions:
• The matrix is always sorted in non-increasing order both row-wise and column-wise.
• All values in the grid are integers.
• Input: Example 1: grid = [[7, 5, 3, -1], [6, 4, 2, -1], [3, 1, -2, -3], [-1, -2, -3, -4]]
• Explanation: In this matrix, there are 8 negative numbers, which are counted and returned as the result.
• Input: Example 2: grid = [[1, 0], [0, 0]]
• Explanation: This matrix has no negative numbers, so the result is 0.
Approach: To solve the problem efficiently, we can leverage the sorted nature of the matrix. By using binary search or row-wise iteration, we can quickly count the number of negative numbers.
Observations:
• The matrix is sorted both row-wise and column-wise, which provides an opportunity for optimization.
• We can use binary search to quickly locate the first negative number in each row.
• Iterating over the rows and applying binary search to count negative numbers in each row would reduce the time complexity.
Steps:
• 1. Iterate through each row of the matrix.
• 2. Use binary search to find the first negative number in each row.
• 3. Add the number of negative numbers in each row to the result.
Empty Inputs:
• Empty grid: No numbers, so the result should be 0.
Large Inputs:
• Grid with the maximum size (100x100): The algorithm should handle this efficiently.
Special Values:
• Grids with no negative numbers: Ensure the result is 0.
Constraints:
• Ensure that the solution handles both small and large grids within the given constraints.
int countNegatives(vector<vector<int>>& grid) {
int res = 0, m = grid.size();
for(int i = 0; i < m; i++) {
auto it = upper_bound(grid[i].rbegin(), grid[i].rend(), -1);
if(*grid[i].rbegin() > -1) continue;
res += it - grid[i].rbegin();
}
return res;
}
1 : Function Declaration
int countNegatives(vector<vector<int>>& grid) {
Declares a function that takes a 2D vector grid as input and returns the count of negative numbers.
2 : Variable Initialization
int res = 0, m = grid.size();
Initializes a result variable to store the count of negative numbers and retrieves the number of rows in the grid.
3 : Loop Iteration
for(int i = 0; i < m; i++) {
Iterates through each row of the grid using a for loop.
4 : Upper Bound Search
auto it = upper_bound(grid[i].rbegin(), grid[i].rend(), -1);
Uses the `upper_bound` function on the reversed row to locate the first element greater than -1.
5 : Condition Check
if(*grid[i].rbegin() > -1) continue;
Skips processing the row if the last element is greater than -1, as it indicates no negatives are present.
6 : Negative Count Update
res += it - grid[i].rbegin();
Adds the count of negative numbers in the current row to the result by calculating the difference between iterators.
7 : Return Statement
return res;
Returns the total count of negative numbers found in the grid.
Best Case: O(m log n) where m is the number of rows and n is the number of columns.
Average Case: O(m log n) for each row search.
Worst Case: O(m log n) due to the binary search for each row.
Description: The binary search reduces the time complexity of checking each row from O(n) to O(log n), making it more efficient for larger grids.
Best Case: O(1)
Worst Case: O(1) as we are only using a constant amount of extra space.
Description: The space complexity is constant, as we only need a few variables to keep track of the count.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus