Set every cell in matrix to 0 if that row or column contains a 0

This cannot be done in one pass since a single bit has an effect on bits before and after it in any ordering. IOW Whatever order you traverse the array in, you may later come accross a 0 which means you have to go back and change a previous 1 to a 0.

Update

People seem to think that by restricting N to some fixed value (say 8) you can solve this is one pass. Well that's a) missing the point and b) not the original question. I wouldn't post a question on sorting and expect an answer which started "assuming you only want to sort 8 things...".

That said, it's a reasonable approach if you know that N is in fact restricted to 8. My answer above answers the original question which has no such retriction.

Ok, so I'm tired as it's 3AM here, but I have a first try inplace with exactly 2 passes on each number in the matrix, so in O(NxN) and it is linear in the size of the matrix.

I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.

The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.

I doubt strongly that I can be done in 1 pass as squares in the beginning depend on squares in the end. Maybe my 2nd pass can be made more efficient...

import pprint

m = [[1, 0, 1, 1, 0],
     [0, 1, 1, 1, 0],
     [1, 1, 1, 1, 1],
     [1, 0, 1, 1, 1],
     [1, 1, 1, 1, 1]]



N = len(m)

### pass 1

# 1 rst line/column
c = 1
for i in range(N):
    c &= m[i][0]

l = 1
for i in range(1,N):
    l &= m[0][i]


# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][j] == 0:
            m[0][j] = 0
            m[i][0] = 0
        else:
            m[i][j] = 0

### pass 2

# if line1 and col1 are ones: it is 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][0] & m[0][j]:
            m[i][j] = 1

# 1rst row and col: reset if 0
if l == 0:
    for i in range(N):
        m [i][0] = 0

if c == 0:
    for j in range(1,N):
        m [0][j] = 0


pprint.pprint(m)