Can we compute this in less than O(n*n) ...( nlogn or n)

Question

This is a question asked to me by a very very famous MNC. The question is as follows ...

Input an 2D N*N array of 0's and 1's. If A(i,j) = 1, then all the values corresponding to the ith row and the jth column are going to be 1. If there is a 1 already, it remains as a 1.

As an example , if we have the array

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

we should get the output as

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

The input matrix is sparsely populated.

Is this possible in less than O(N^2)?

No additional space is provided was another condition. I would like to know if there's a way to achieve the complexity using a space <= O(N).

P.S : I don't need answers that give me a complexity of O(N*N). This is not a homework problem. I have tried much and couldn't get a proper solution and thought I could get some ideas here.Leave the printing aside for the complexity

My rough idea was to may be dynamically eliminate the number of elements traversed restricting them to around 2N or so. But I couldn't get a proper idea.

Answer 1

Hii guys ,

thanks to the comment from mb14 i think i could get it solved in less than O(NN) time... The worst would take O(NN)...

Actually , we have the given array suppose

  1 0 0 0 1
  0 1 0 0 0 
  0 1 1 0 0 
  1 1 1 0 1
  0 0 0 0 0 

Lets have 2 arrays of size N (this would be the worst case) ... One is dedicated for indexing rows and other columns... Put those with a[i][1] = 0 in one array and then a[1][j] =0 in another..

Then take those values only and check for the second row and colums...In this manner , we get the values of rows and colums where there are only 0;'s entirely...

The number of values in the row array gives number of 0's in the result array and the points a[row-array values][column array value] gives you those points ....

We could solve it in below O(NN) and worst is O(NN) ... As we can seee , the arrays ( of size N) diminishes ....

I did this for a few arrays and got the result for all of them ... :)

Please correct me if i am wrong anywhere...

Thanx for all your comments guys...You are all very helpful and i did learn quite a few things along the way ... :)