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

In the worst case, you may need to toggle N * N - N bits from 0 to 1 to generate the output. It would seem you're pretty well stuck with O(N*N).