How to Count Negative Numbers in a Sorted Matrix? [Solved] (Amazon Coding Question)

Anyway, instead of focusing on whether this coding problem was asked in
Amazon or not, let’s focus on how we can solve this problem, but before
that, let’s revise the problem statement and see a couple of examples.

Example – If the given matrix is below then the total number of negative
numbers is 3 as there are three negative numbers 2 in the first row (-5 and
-2) And one in the second row (-2). 

[-5, -2, 3]

[-2, 3, 4]

[3, 4, 5]

How to count negative numbers in a sorted matrix?

Before we think about the solution, let’s first think about all the
information which is available to you. For example, matrix is sorted, it
contains numbers, how big can be that its another question and it contains
both positive and negative numbers. 

This will help you to find a solution
quickly.   

Well, there are a couple of ways to solve this problem and we will them.
First, let’s start with the brute first solution as we do always. 

Solution 1: Brute force or Naive solution

The easiest way to solve this problem is going through each element and
counting whether the number is negative or not, but that means it would take
O(N*M) times where N is a number of rows and M is a number of columns. If
N=M then O(n^2) is not an optimal
solution. 

Can we do this better?

Solution 2: Optional Solution

In our example, it would be the second element in the first rows, which
means there will be only two negative numbers in the first row. 

Now, if move to the same index in the next row, and do this again, we’ll
reach -2 and that is the first element in the second row, so in total now we
have 2 + 1 = 3 negative numbers. In the last rows, if we start with the same
index, it’s a positive number so we are done already. Answer would be 3
negative numbers.

This is
possible because each row and column are sorted in increasing order.
This means anything earlier -2 in the row will be negative, and anything
below will also be greater than it. 

That’s why when we started with the second row, we didn’t start with the
last element of the second row again, because it cannot be negative, since
columns are also sorted on increasing order and the first element in the
last column was positive.

The time complexity of this problem is
O(N+M) where N is the number of
rows and M is the number of columns, which means it’s much better than the
earlier solution. 

Java Program to count negative numbers in a sorted matrix

import static org.junit.Assert.assertEquals;

import org.junit.Before;
import org.junit.Ignore;
import org.junit.Test;
/*
* Problem - find the first recurring character in given String
* Examples
* if given String is "ABCDA" return "A"
* if given String is "ABCDAB" return "A"
* if given String is "ABBCDA" return "B"
* if given String is "ABCD" return null
*/
public class GoogleTest {
AmazonQuestion _instance;

@Before
public void init(){
_instance = new AmazonQuestion();
}

@Test
public void testBrutForceSolution(){

assertEquals(0, _instance.bruteForce(new int[][]{}, 0, 0));
assertEquals(1, _instance.bruteForce(new int[][]{{-1, 0}, {0, 1}}, 2, 2));
assertEquals(3, _instance.bruteForce(
new int[][]{{-2, -1, 0}, {-1, 0, 1}}, 2, 3));
assertEquals(5, _instance.bruteForce(
new int[][]{{-3, -2, 1}, {-2, -1, 0}, {-1, 0, 1}}, 3, 3));
assertEquals(0, _instance.bruteForce(
new int[][]{{7, 8, 9}, {8, 9, 10}, {9, 10, 11}}, 3, 3));
assertEquals(9, _instance.bruteForce(
new int[][]{{-6, -5, -4}, {-5, -4, -3}, {-4, -3, -2}}, 3, 3));
}

@Test
public void testOptimalSolution(){
assertEquals(0, _instance.optimalSolution(new int[][]{}, 0, 0));
assertEquals(1, _instance.optimalSolution(new int[][]{{-1, 0}, {0, 1}}, 2, 2));
assertEquals(3, _instance.optimalSolution(
new int[][]{{-2, -1, 0}, {-1, 0, 1}}, 2, 3));
assertEquals(5, _instance.optimalSolution(
new int[][]{{-3, -2, 1}, {-2, -1, 0}, {-1, 0, 1}}, 3, 3));
assertEquals(0, _instance.optimalSolution(
new int[][]{{7, 8, 9}, {8, 9, 10}, {9, 10, 11}}, 3, 3));
assertEquals(9, _instance.optimalSolution(
new int[][]{{-6, -5, -4}, {-5, -4, -3}, {-4, -3, -2}}, 3, 3));
}


}


class AmazonQuestion {

public int bruteForce(int[][] matrix, int rows, int columns){
int total = 0;

for(int i=0; i= 0){
if(matrix[i][j] < 0){
total = total + j + 1;
i++;
}else{
j--;
}
}

return total;
}


}

Output: All tests passed

Each test has four assertions or conditions to check, which are an actual
test for logic implemented in brute force and our optimal solution, which
includes testing for an empty array, testing of the array with both positive
and negative numbers, testing for an array with only positive and negative
numbers, and testing with an array of different length.

That’s all about
how to count a total number of negative integers in a given Matrix
where both rows and columns are sorted in ascending order. We have discussed
two solutions, Brute force checks every element to see if it’s negative or
not, while the optimal solution only checks almost half of the elements. 

It
takes advantage of the fact that rows and columns of the matrix are already
sorted in ascending order.