Amazon Interview Question
Software Engineer / Developers@Anonymous
Yes...this is the solution that I gave initially. I guess this solution can be further optimised using binary search
Worst case is O(n^2) when all the negative elements are in the first column.....
binary search on each row or column will give O(nlogn)
@Anonymous
please try to run this soln on any example..
count = count + (col + 1);
????????????????
@A
hows the worst case O(n^2) when all negative elements are in the first column? In that case it would be O(n+n-1) which O(n).
@above
count= count + (col+1) .. tht s cause if at a specific col value a number is neg the numbers on the same line i.e. row in all prev cols are neg too as it is sorted..
@A
hows the worst case O(n^2) when all negative elements are in the first column? In that case it would be O(n+n-1) which O(n).
@above
count= count + (col+1) .. tht s cause if at a specific col value a number is neg the numbers on the same line i.e. row in all prev cols are neg too as it is sorted..
Assume the elements in the row and the column are sorted in increasing order.
Case 1: Now compare the element [0,0].. if it is greater thean zero.. it means all the elements are +ve.. so number of negetive integers=0\
Case: if [0.0] element is a -ve number.
In this case, we will start our search from [n,n].. if array[n,n] is -ve.. it means all the numbers in the array are negetive. If array[n,n] is +ve, then move a level up diagonally, i.e move to [n-1,n-1]... move up one level till u find a -ve number. If suppose we find a -ve number at [i,i] it means all the numbers in that square matrix with indices i,i are -ve. Now will have to only check for the next column and next row for the number of -ve numbers. So, if we have a -ve number at [i,i], then number of -ve numbers in the array = i*i + (number of -ve elenments in row i+1) + (number of -ve elenments in column i+1). this can be doen in O(n).
Finding the first negative number at [i,i] only means that the sub-matrix with row and column indices from i through n has only one negative element. We shouldn't ignore other elements, say the element at [m,n] where m<i, n>i. For example,
The above algorithm will not work for the following case.
Assume n=4 and the matrix is
-30, -29, -28, -27
-29, -28, +30, +40
+30, +40, +50, +60
+44, +55, +65, +75
Applying the above algorithm will result in i=2. So, according to the given algorithm, number of negative elements will be
(2*2) + (no. of negative elements in row 3) + (no. of negative elements in column 3)
= 4 + 0 + 1
= 5
But, the last element in first row is unaccounted for.
My algorithm is as follows.
Do a binary search for the first positive number in every row. If the index is i, the number of negative elements in that row will be i-1.
Do this for all the n rows. Complexity is (n * log(n)).
Perhaps we can merge this and the above idea to produce an even better algorithm.
# O(n)
def countneg(a):
count = 0
j = len(a[0])
for i in xrange(len(a)):
while j > 0 and a[i][j - 1] >= 0:
j -= 1
count += j
return count
mat = [[-5, 0, 1], [-2, 1, 2], [-1, 2, 3]]
print countneg(mat)
# 3
If n is the number of elements in a row or column then ur algorithm is O(n^2).. the above solutions seem to have O(nlogn) in that case.. Going to each element is surely not an efficient solution.. ur not making use of the sorted property..
How about doing binary search for finding the first positive in a row a, say at (i,j) and then eliminating submatrix of positives (n-i,n-j). And then moving to next row and doing the same.
Worst case would still be nlogn if there are no positives at all in the matrix.
My take:
1. start from topmost and leftmost element of matrix M.
2. As a post above mentions, iff M[0][0] is >= 0, no. of -ve elements = 0;
3. if step 2 is not true, start from M[0][0] and search non-negative no. row wise.
3a. On finding first non-negative no. , mark the corresponding column number.
Elements in that column are all non-negative.
3b. Let say a non-negative no. is found at column (m+1). Then for each of the remaining rows, search operation is to be performed till m column.
3c. In this case worst case search will be O(mn).
My solution is:
1) scan first row till you don't find a positive number. Suppose you found it at a[m][n].
2) Now check a[m+1][n] element.
a)If it is -ve then go to next row but same column till you don't find +ve or end.
b) If it is +ve then scan left until you can't find -ve.
Repeat step 2.
This is an elegant solution
public static void main(String[] args) {
int [][] a = new int[][] {{-30,-29,-28,-27},{-29,-28,30,40},{30,40,50,60},{44,55,65,75}};
int n = 4;
int i = 0;
int j = n-1;
int sum = 0;
while(j>-1 && i<n)
{
if(a[i][j]<0)
{
sum = sum + j+1;
i++;
}
else
{
j--;
}
}
System.out.println(sum);
}
Algorithm:
1. Search for an element M(a, b) on the diagonal of Matrix(n * n) that all M(i,j) that i<a, j<b has M(i,j)>0 and all M(i,j) that i>a, j>b has M(i, j)<0.
Search for element M(a, b) will take O(lgn) time.
2. Add the size of Matrix(n-a, n-b) to the total count
3. Divide the original Matrix into two subMatrixes M1=M(a to n, 0 to b) and M2=M(0 to a, b to n)
4. Do step 1-3 recursively to M1 and M2 till M1 and M2 could not be found any more.
Worst Case Time complexity: T(n) = 2T(n/2) + lg(n) = O(n)
It doesn't matter if the sub-matrices are square or not. We just need to find a position (a,b) on the diagonal which satisfy M(i,j) that i<a, j<b has M(i,j)>0 and all M(i,j) that i>a, j>b has M(i, j)<0.
For a sub-matrix which is not a square, you may get a search point (5/2, 3), then just search both (2,3) and (3,3) -- it's still constant time.
int FindNegative(int M[][], int top, int left, int bottom, int right)
{
if (top <= bottom && left <= right)
{
int center = M[(top + bottom)/2][(left+right)/2];
if (center > 0)
{
return FindNegative(M, top, left, (top+bottom)/2, (left+righ)/2) +
FindNegative(M, top, (left+right)/2 + 1, (top+bottom)/2 -1, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 -1);
}
return ((top+bottom)/2 +1 )*((left + right)/2+1) +
FindNegative(M, top, (left+right)/2 + 1, bottom, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 );
}
}
int FindNegative(int M[][], int top, int left, int bottom, int right)
{
if (top <= bottom && left <= right)
{
int center = M[(top + bottom)/2][(left+right)/2];
if (center > 0)
{
return FindNegative(M, top, left, (top+bottom)/2, (left+righ)/2) +
FindNegative(M, top, (left+right)/2 + 1, (top+bottom)/2 -1, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 -1);
}
return ((top+bottom)/2 +1 )*((left + right)/2+1) +
FindNegative(M, top, (left+right)/2 + 1, bottom, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 );
}
return 0;
}
<pre lang="java" line="1" title="CodeMonkey91820" class="run-this"> class CountNegative {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] aMatrix = { { -9, -3,- 2, 120 }, { -8, -2, 30, 230 },
{ -7, -1, 40, 420 }, { -6, 90, 91, 520 } };
int negCount = countNegative(aMatrix);
System.out.print(negCount);
}
private static int countNegative(int[][] aMatrix) {
// TODO Auto-generated method stub
int i = 0;
int j = aMatrix[0].length - 1;
while (aMatrix[i][j] >= 0 && j > 0)
j--;
if (j < 0)
return 0;
int count = j + 1;
i++;
while (i < aMatrix.length) {
if (aMatrix[i][j] >= 0) {
j--;
} else {
while (aMatrix[i][j] < 0 && j < aMatrix[0].length)
j++;
count = count + j;
i++;
}
}
return count;
}
}
</pre><pre title="CodeMonkey91820" input="yes">1
2
10
42
11
</pre>
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int a[4][4] =
{
{-15, -10, 4, 6},
{-10, -3, 7, 10},
{-5, -1, 12, 15},
{-3, -2, 15, 20}
};
int m=4, n=4, num=0, count=0;
for(int i=0, j=n-1; i<m && j>=0; )
{
if(num > a[i][j])
{
i++;
count += (j+1);
}
else
j--;
}
cout << count << endl;
return 0;
}
def countNegInRowColSortedMatrix(matr):
row = 0;
col = len(matr[0]) - 1;
countNeg = 0;
while(row < len(matr) and col >= 0):
while col >= 0 and matr[row][col] >= 0 :
col = col - 1;
countNeg = countNeg + col + 1;
row = row + 1;
return countNeg;
matr = [[-100, -20, -10],
[-5, -7, 0],
[-4, -2, 42]];
print countNegInRowColSortedMatrix(matr);
int countNegatives(int array[][], int size) {
- Anonymous February 07, 2010int col = size - 1, row = 0;
int count = 0;
while(row < size && col >= 0) {
if(array[row][col] < 0 ) {
count = count + (col + 1);
row = row + 1;
}
else {
col = col - 1;
}
}
return count;
}