Amazon Interview Query – How one can Rely Detrimental Numbers in a Sorted Matrix? [Solved]

Instance – If the given matrix is beneath then the whole variety of unfavourable
numbers is 3 as there are three unfavourable numbers 2 within the first row (-5 and
-2) And one within the second row (-2). 

[-5, -2, 3]

[-2, 3, 4]

[3, 4, 5]

How one can rely unfavourable numbers in a sorted matrix?

Earlier than we take into consideration the answer, let’s first take into consideration all of the
data which is on the market to you. For instance, matrix is sorted, it
incorporates numbers, how large may be that its one other query and it incorporates
each constructive and unfavourable numbers. It will aid you to discover a resolution
shortly.   

Effectively, there are a few methods to unravel this downside and we’ll them.
First, let’s begin with the brute first resolution as we do all the time. 

Resolution 1: Brute pressure or Naive resolution

The simplest method to remedy this downside goes by means of every ingredient and
counting whether or not the quantity is unfavourable or not, however meaning it might take
O(N*M) occasions the place N is plenty of rows and M is plenty of columns. If
N=M then O(n^2) will not be an optimum
resolution. 

Can we do that higher?

Resolution 2: Non-compulsory Resolution

In our instance, it might be the second ingredient within the first rows, which
means there will likely be solely two unfavourable numbers within the first row. 

Now, if transfer to the identical index within the subsequent row, and do that once more, we’ll
attain -2 and that’s the first ingredient within the second row, so in complete now we
have 2 + 1 = 3 unfavourable numbers. Within the final rows, if we begin with the identical
index, it is a constructive quantity so we’re finished already. Reply could be 3
unfavourable numbers.

That is
attainable as a result of every row and column are sorted in rising order.
This implies something earlier -2 within the row will likely be unfavourable, and something
beneath will even be higher than it. 

That is why after we began with the second row, we did not begin with the
final ingredient of the second row once more, as a result of it can’t be unfavourable, since
columns are additionally sorted on rising order and the primary ingredient within the
final column was constructive.

The time complexity of this downside is
O(N+M) the place N is the variety of
rows and M is the variety of columns, which suggests it is a lot better than the
earlier resolution. 

Java Program to rely unfavourable numbers in a sorted matrix

import static org.junit.Assert.assertEquals;

import org.junit.Earlier than;
import org.junit.Ignore;
import org.junit.Take a look at;
/*
* Drawback - discover the primary 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;

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

@Take a look at
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));
}

@Take a look at
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 complete = 0;

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

return complete;
}


}

Output: All assessments handed

Every check has 4 assertions or situations to test, that are an precise
check for logic applied in brute pressure and our optimum resolution, which
contains testing for an empty array, testing of the array with each constructive
and unfavourable numbers, testing for an array with solely constructive and unfavourable
numbers, and testing with an array of various size.

That is all about
tips on how to rely a complete variety of unfavourable integers in a given Matrix
the place each rows and columns are sorted in ascending order. We have now mentioned
two options, Brute pressure checks each ingredient to see if it is unfavourable or
not, whereas the optimum resolution solely checks nearly half of the weather. It
takes benefit of the truth that rows and columns of the matrix are already
sorted in ascending order.