The “Count Negative Numbers in a Sorted Matrix” problem involves counting how many numbers in a given matrix are negative. The matrix is sorted in a specific way: each row is sorted in non-increasing order (from left to right), and each column is sorted in non-increasing order (from top to bottom).
Problem Statement
Given a m x n matrix where each row and each column is sorted in descending order, count how many negative numbers are in the matrix.
Example
For the matrix:
[
[4, 3, 2, -1],
[3, 2, 1, -1],
[1, 1, -1, -2],
[-1, -1, -2, -3]
]
The negative numbers are -1, -1, -1, -2, -1, -2, and -3, totaling 7.
C# Implementation
Here’s how to implement this in C#:
using System;
public class CountNegativeNumbers
{
public static int CountNegatives(int[][] grid)
{
int count = 0;
int rows = grid.Length;
int cols = grid[0].Length;
// Start from the top-right corner of the matrix
int row = 0, col = cols - 1;
while (row < rows && col >= 0)
{
if (grid[row][col] < 0)
{
// If the current element is negative, all elements below in the column are also negative
count += (rows - row);
col--; // Move left
}
else
{
row++; // Move down
}
}
return count;
}
public static void Main(string[] args)
{
int[][] grid = new int[][]
{
new int[] { 4, 3, 2, -1 },
new int[] { 3, 2, 1, -1 },
new int[] { 1, 1, -1, -2 },
new int[] { -1, -1, -2, -3 }
};
int result = CountNegatives(grid);
Console.WriteLine($"The number of negative numbers in the matrix is: {result}");
}
}
Explanation
-
Data Structure:
- The matrix is represented as a jagged array (
int[][]
), where each inner array represents a row.
- The matrix is represented as a jagged array (
-
CountNegatives Method:
- This method counts the negative numbers in the matrix using an efficient approach.
- It starts from the top-right corner of the matrix (
grid[row][col]
) and iterates through the matrix:- If the current element is negative, all elements below it in that column are also negative (due to the sorting). Therefore, we add the count of those elements (which is
rows - row
) to thecount
and move left by decrementingcol
. - If the current element is non-negative, we move down to the next row by incrementing
row
.
- If the current element is negative, all elements below it in that column are also negative (due to the sorting). Therefore, we add the count of those elements (which is
- The loop continues until we go out of bounds (either moving past the last row or the first column).
-
Main Method:
- It initializes a sample matrix and calls the
CountNegatives
method. - Finally, it prints the number of negative numbers found.
- It initializes a sample matrix and calls the
Complexity
- Time Complexity: O(m + n), where
m
is the number of rows andn
is the number of columns. In the worst case, we traverse all rows and columns once. - Space Complexity: O(1) since we are using a constant amount of additional space for counters.
Output
When you run the program, it will display:
The number of negative numbers in the matrix is: 8
This implementation effectively counts the negative numbers in a sorted matrix by leveraging the sorting properties, making it much more efficient than a straightforward iteration through all elements.