Algorithm: how to find a column in matrix filled with all 1, time complexity O(n)?
algorithm, matrix
Solution
Let me take a very wild guess on what you are trying to do. Hint from the mention of:
- The array represent relation on people
- You are finding a column with all 1s
- 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.
Problem
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(n2); - 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(n2); Any other solutions?