Count Negative Integers In A Sorted 2D Array

In this blog, you will learn how to Count Negative Integers In A Sorted 2D Array.

Problem Statement

 

Given a sorted 2-D array, find the number of negative integers present in the 2-D array. Solving this is pretty easy but the point is that Amazon asked this question in their interview, so it's not just meant to be solved but rather solved efficiently. Let's look at some sample cases, 

int[,] matrix = new int[,]
{
    { -5, -3, -2, 0, 4 },
    { -1, 0, 1, 3, 4 },
    { 3, 5, 6, 8, 9 },
};
int result = CountNegatives(matrix);
//result should be 4 since it has 4 negative integers

Approach 1

 

The most straightforward way to approach this problem is by looping over all the elements and keeping the count for all the elements less than zero. This approach is rather an inefficient one as its time complexity is,

 

Time Complexity = O(numberOfRows * numberOfColumns)

 

We have to traverse over all the elements until the end of the matrix to check for any negative intergers, hence proving this algorithm is an inefficient one. Here's a sample code in C# that demonstrates this algorithm,

static int Approach1(int[,] matrix)
{
    int count = 0;
    foreach (int element in matrix)
    {
        if (element < 0)
            count++;
    }
    return count;
}

Approach 2

 

Another way to solve this problem is by looping over the matrix in reverse order and using the given information 'sorted' to make the algorithm more efficient. We loop over every row from the last element to the first, and if we encounter any negative integer we add that index to the counter and then break the loop.

 

Time Complexity = O(numberOfRows + numberOfColumns)

 

This is an efficient solution to this interview question which takes the least time to process. This algorithm is implemented in the C# code below,

static int Approach2(int[,] matrix)
{
    int count = 0;
    for (int row = 0; row < matrix.GetLength(0); row++)
    {
        for (int column = matrix.GetLength(1) - 1; column >= 0; column--)
        {
            if (matrix[row, column] < 0)
            {
                count += column + 1;
                break;
            }
        }
    }
    return count;
}