Можем ли мы вычислить это менее чем за O (n * n)… (nlogn или n)

Это вопрос, который мне задает очень известный MNC. Вопрос в следующем ...

Введите двумерный массив N * N из нулей и единиц. Если A (i, j) = 1, то все значения, соответствующие i-й строке и j-му столбцу, будут равны 1. Если уже есть 1, она останется как 1.

В качестве примера, если у нас есть массив

  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

, мы должны получить вывод как

 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

Входная матрица редко заполнена.

Возможно ли это меньше, чем за O (N ^ 2)?

Дополнительное пространство не предоставляется, было другое условие . Я хотел бы знать, есть ли способ достичь сложности, используя пробел <= O (N).

PS: Мне не нужны ответы, которые дают мне сложность O (N * N). Это не домашнее задание. Я много пробовал, но не смог найти правильного решения и подумал, что могу почерпнуть здесь несколько идей. Оставьте печать в стороне из-за сложности

Моя приблизительная идея заключалась в том, чтобы можно было динамически исключить количество пройденных элементов, ограничив их примерно 2N или около того. Но я так и не понял.