Algorithm: how to find a column in matrix filled with all 1, time complexity O(n)?

Question

I have a matrix which looks like this:

| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |

I should find if this matrix has a column filled with all 1. At this matrix it's column 4. And it's said that time complexity is O(n) and memory is O(1).

This matrix represents a binary relation on a set (of people). n is the size of the set, so the size of the matrix is n * n.

I can see 2 possible solutions:

• Take the first column, go through it, if see zero, jump on the next column and so on. But the worst case of this algorithm will be O(n²);
• The next one, if I will have a sum of all columns than I can give an answer in O(n). But it's not said at task conditions that we have computed sums. And if I will compute them, the complexity will be also O(n²);

Any other solutions?

Answer 1

Assuming arbitrary content, you cannot avoid a worst-case of O(n²).^* You have to visit every element in each column that you want to consider, and in the worst-case, you have to consider all columns.

---

_{* Also assuming that n is the matrix dimension here, not the total number of elements.}

Answer 2

Let me take a very wild guess on what you are trying to do. Hint from the mention of:

1. The array represent relation on people
2. You are finding a column with all 1s
3. You are trying to find an O(n) algorithm

Well, you can not do that in O(n) and I can prove that it is O(n^2) only.

But my wild guess is that you doing a classic celebrity identification problem, and that you misunderstood the problem.

A celebrity is person that is known by every other person, but doesn't know any [other people].

I celebrity identification problem, you are trying to find something like:

Find the number i where
a[i][x] = 1 for all x            -> every one knows the celebrity
a[x][i] = 0 for all x != i       -> the celebrity doesn't know anyone else

And indeed with this extra constrain on what you are trying to find, there is an O(n) solution.

Answer 3

If you don't assume arbitrary content (as in Oli's answer) and you can encode each row as an unsigned integer with binary flags, then you can do it in O(n) and O(1) by just repeatedely performing a logical AND of each row with the latest result.

The final set of flags will only have ones where the relevant column was also one.