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 becuase 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 Matrics-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, matrics are 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. Anwer 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, Bruteforce 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.

## No comments :

## Post a Comment