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

Hello guys, earlier I shared a list of Google Coding Interview questions, and today, I am going to share with you an interesting coding problem which was asked on Amazon, how to count total negative numbers in a given matrix where rows and columns are sorted in increasing order. Again, I found this coding problem while surfing on the internet, It wasn't actually asked to me or my reader, so I can't vouch that it's actually an Amazon Interview question. Though, I really expect it to be because it's an interesting problem and the optimal solution is not so easy but with the internet, you never know.

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.

Problem - Write a program in your favorite programming language (Java, Python, Ruby, C++, JavaScript, or whatever) to count a total number of negative integers in a matrix where rows and columns are sorted in increasing order.

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]

Now, let's see how you can solve this one of the popular Matrix -based coding interview problem. By the way, if you are new to data structure and algorithms or want to refresh your data structure concepts, I also suggest you join any good online course. If you need recommendations, see these top data structure and algorithms courses for Java developers to start with. 

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 the first solution, we are not using the fact that rows and columns of the matrix are in sorted order. If you consider that fact, we may come with a better solution. Let's assume we start with the last column in the first rows and go backward to find the last negative number in that list.

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. 

By the way, if you struggle to calculate the time and space complexity of your solution or any algorithm or if you want to learn more about then you can also check out these best data structure courses to start with. 

Java Program to count negative numbers in a sorted matrix

Now that you understand the logic, let's write down both brute force and this optimal solution in your favorite programming languages like Java or Python. Since I love Java, I am going to write the solution in Java, you may do it on Python, C++, Ruby, or JavaScript whatever you like.

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

When you run this program as a JUnit test, you will find that all tests are passing which means our solution is good. If you look closely, you will find that I have two tests, one for each solution, I mean one for brute force and one for the optimal solution. 

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.

Other Coding Problems from Interviews for Practice

If you are interested in solving more String based coding problems from Google, Facebook, Amazon, and other FAANG companies then here is the list of most popular string questions

• How to check if a string contains only digits?  (solution)
• How to count the number of vowels and consonants in a String? (solution)
• How to count the occurrence of a given character in String? (solution)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to reverse words in a sentence without using a library method? (solution)
• How to check if String is Palindrome? (solution)
• How to find the first recurring character from a given String in Java? (solution)
• How to find all permutations of String? (solution)
• How to check if the given String is the rotation of each other? [solved]
• How to Print duplicate characters from String? (solution)
• How to convert a numeric string to an int? (solution)
• How to check if two Strings are anagrams of each other? (solution)
• How to program to print the first non-repeated character from String? (solution)
• How to reverse String in Java using Iteration and Recursion? (solution)
• How to return the highest occurred character in a String? (solution)
• How to reverse a String in place in Java? (solution)
• 50+ Data Structure and Algorithms Interview Questions (questions)

Thanks for reading this article so far. If you like this Amazon coding Interview problem and my solution and explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are preparing for an interview, take this FAANG Interview preparation course which can your an idea about what kind of questions comes on FAANG interviews and how to solve them in a limited time. There was a time when finding good resources was very hard but you can now crack the FAANG interview by using these kinds of resources. 

P.S.S. - If you feel your data structure and algorithm skills are rusty and you need a bit of refresher then I suggest you take this free data structure and algorithms course to quickly revise all important concepts.