Negative Numbers Count - C++ Solution

1. Introduction

In this post, we'll tackle a matrix traversal problem that involves counting negative numbers in a sorted matrix. This problem is interesting as it combines concepts of matrix traversal and efficient searching due to the sorted nature of the matrix.

Problem

Given an M × N matrix sorted both row-wise and column-wise, the objective is to find the total number of negative numbers in the matrix in linear time.

2. Solution Steps

1. Start from the top-right corner of the matrix.

2. If the current element is negative, increment the count of negative numbers and move down to the next row.

3. If the current element is non-negative, move left to the next column.

4. Repeat steps 2 and 3 until the boundaries of the matrix are reached.

5. The count obtained at the end is the total number of negative numbers in the matrix.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to count negative numbers in a sorted matrix
int countNegatives(const vector<vector<int>>& matrix) {
    int M = matrix.size();
    int N = matrix[0].size();
    int count = 0;
    int row = 0, col = N - 1;

    while (row < M && col >= 0) {
        if (matrix[row][col] < 0) {
            count += (col + 1);
            row++;
        } else {
            col--;
        }
    }

    return count;
}

int main() {
    vector<vector<int>> matrix = {
        {-7, -3, -1, 3, 5},
        {-3, -2,  2, 4, 6},
        {-1,  1,  3, 5, 8},
        { 3,  4,  7, 8, 9}
    };

    cout << "Number of negative numbers: " << countNegatives(matrix) << endl;
    return 0;
}

Output:

Number of negative numbers: 6

Explanation:

The function countNegatives efficiently counts the negative numbers in the sorted matrix by starting from the top-right corner. It moves left if the current element is non-negative and moves down if the current element is negative, adding the column index to the count. This approach takes advantage of the sorted nature of the matrix and performs the count in linear time. For the given matrix, there are 6 negative numbers.