Count negative numbers in a sorted matrix problem in C#

General
1

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

  1. Data Structure:

    • The matrix is represented as a jagged array (int[][]), where each inner array represents a row.

  2. 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 the count and move left by decrementing col.
      • If the current element is non-negative, we move down to the next row by incrementing row.
    • The loop continues until we go out of bounds (either moving past the last row or the first column).

  3. Main Method:

    • It initializes a sample matrix and calls the CountNegatives method.
    • Finally, it prints the number of negative numbers found.

Complexity

  • Time Complexity: O(m + n), where m is the number of rows and n 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.