CareerCup

Approach: Assuming indexes in the range 1...N,start at (1,N) ,i.e. right hand top and check if the element is negative.If yes,obviously all the elements on its left including itself would be -ve.So set the count_of_negatives to N and increment the row_index.If a(1,N) is >=0,decrement the col_index.

So at any general grid point , if a(row,col)< 0, increment row by 1 and count_of_negatives by col,because all the elements to the left of a(row,col) including itself in the same row would be < 0. On the other hand if a(row,col) >=0, just decrement col. Execute the above in a loop till you transcend the boundaries of the matrix.

Time Complexity is 2n which is O(n),where n is number of rows(cols) in the square matrix

The pseudocode is

numNegatives(a[1..N][1...N]){

if a(1,1) >= 0 return 0;

if a(N,N) < 0 return N*N;

row = 1
col = N
count = 0; //count is the number of negatives in the matrix
while( row <=N && col >= 1 ){
if(a(row,col) < 0){
count += col; //everything on the left of a(row,col)including itself are -ve
row++;
}else{
col--;
}
}

return count;
}

rough idea:

M row, N column

1.start from right-bottom corner, go up and check the 1st element <0, if not found, proceed to next column
2.when the 1st elem that < 0 is found, record it - say (i,j), and go downward to (i-1,j) and then go left and check the 1st elem <0;

repeat 1,2 and we are basically tracking the right-bottom position of the area with all -ve numbers.

worst case O(MN),

improvement can be done by using binary search when checking the 1st -ve number at each row/column

I would start with this. I wonder about complexity - is it really O(log N)?

static class Program
{
    // Test data.
    static int[,] array = { { -2, -1, 3 }, { -1, 0, 4 }, { 1, 3, 5 } };

    // Counts the number of negative elements in a given (sub)rectangle.
    static int CountNegatives(int row, int col, int rowCount, int colCount)
    {
        // Make sure the area is not empty.
        if (rowCount == 0 || colCount == 0)
            return 0;
        
        // Check the bottom-right (largest) element.
        if (array[row + rowCount - 1, col + colCount - 1] < 0)
            return rowCount * colCount; // all numbers are negative

        // Check the top-left (smallest) element.
        if (array[row, col] >= 0)
            return 0;   // all numbers are positive

        // Divide the area into 4 sub-rectangles and process them recursively.
        int dRow = rowCount / 2;
        int dCol = colCount / 2;
        return
            CountNegatives(row, col, dRow, dCol) +
            CountNegatives(row + dRow, col, dRow, dCol) +
            CountNegatives(row, col + dCol, dRow, dCol) +
            CountNegatives(row + dRow, col + dCol, dRow, dCol);
    }

    static void Main(string[] args)
    {
        System.Console.WriteLine(CountNegatives(0, 0, array.GetLength(0), array.GetLength(1)));
    }
}

^ there's an obvious bug there (the rightmost column and the bottom row will be sometimes lost because of the integer division by 2), but I guess the algorithm should work once that bug is fixed.

Given the array, a[n][n],the negative num is Num(Num=0 initally) from the right-top corner, a[0][n-1], check whether it >0 or not, if >=0, move to the lefter one, a[0][n-2], if it < 0, found the first element which >=0 in the same column, suppose it is a[x][n-1], Num+=x*n, Move to the a[x][n-2], do the similar things untill the current element move outside the array. The time complexisty is O(n)

Was this asked in microsoft....?for what position?nice ques though

start with the top right element ...if no neg decrement the col iterator..
if neg means incr count col iterator times..incr the row iterator..repeat till the last row or first col is reached...O(m+n)

The above algorithm assumes it is sorted in the same order(all increase or decrease).

function CountNegatives(arr, row, col):
  count = 0
  for(i = col, j = 1; i >= 1 and j <= row):
    if(arr[j][i] > 0):
      i--
    else
      count += i
      j++
  return count

#include<iostream>
using namespace std;

int findNeg(int Arr[][3])
{
int count = 0,COL=3;
for(int i=0;i<3;i++)
{
if(Arr[i][0]>0)
break;
for(int j=0;j<COL;j++)
{
if(Arr[i][j]>0)
{
COL = j;
break;
}
count++;
}
}
return count;
}

int main()
{
int arr[3][3] = {{-3,-2,-1},{-2,1,3},{1,2,4}};
cout <<"Number of Negative numbers = " <<findNeg(arr);
return 0;
}

http: //webcourse . cs.technion.ac.il/234247/Spring2006/ho/WCFiles/Celebrity . pdf

Guys,
Well, it is definitely O(N) solution. One outstanding property is a diagonal property. So to say, Let cell X = (k,k) be a diagonal cell. No other cell (i,j); i < k, and j < k has a value greater than X. Then the solution is move diagonally from (0,0) bottom-right. Find the last diagonal that still negative, then we are guarantee to have at least (k-1)^2 negative cells. Then count the negative number in column k and row k. The time complexity is sqrt(2N^2) + 2N = O(N).