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

Question

I have a matrix that 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 have to find if this matrix has a column filled with all 1. On this matrix it has column 4. And he said that the time complexity is O (n), and the memory is O (1).

This matrix is ​​a binary relation on a set of (people). n is the size of the set; therefore, the size of the matrix is n * n .

I see two possible solutions:

• Take the first column, go through it, if you see zero, go to the next column and so on. But the worst case of this algorithm is O (n ² );
• Next, if I have the sum of all the columns, than I can give an answer in O (n). But under the conditions of the problem, he did not say that we calculated the amounts. And if I calculate them, the complexity will also be O (n ² );

Any other solutions?

Answer 1

Let me tell you a lot about what you are trying to do. Hint from the mention:

• An array represents an attitude for people.
• You will find a column with all 1s
• You are trying to find the O(n) algorithm

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

But my wild is that you are making the classic problem of identifying celebrities , and that you are an incomprehensible problem.

A celebrity is a person who is known to every other person, but does not know others [other people].

The problem of identifying celebrities, 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 

Indeed, with this additional restriction on what you are trying to find, there is an O(n) solution.

Answer 2

Assuming arbitrary content, you cannot escape the worst case of O (n ² ). ^* You need to visit each item in each column that you want to consider, and in the worst case, you need to consider all the columns.

---

_{* It is also assumed that n is the size of the matrix, not the total number of elements.}

Answer 3

If you do not accept arbitrary content (as in Oli's answer), and you can encode each line as an unsigned integer with binary flags, then you can do this in O (n) and O (1) by simply re-executing the logical AND each line with last result.

In the last set of flags there will be only those where the corresponding column was also one.

Answer 4

What is the input for the matrix?

If you get a number for each column, that is, in your example (in decimal) 14, 8, 4, 31, 1, you can simply create the number a with n binary digits set to 1 (in this case, 31). If this number is equal to one of the column numbers, one of the columns is all 1s.

Answer 5

My solution is that we first assume that all columns have 1s, then we go through the rows, over the possible solutions that we have, and cut the columns that cannot be the solution.

This solution is written in Java:

Solution 1: O (n ^ 2) is straightforward

 public class Main { // Given A: an M x N matrix public static ArrayList<Integer> solve (Integer [][] matrix) { // Assuming all columns have 1s, we have list S ArrayList<Integer> S = new ArrayList<Integer>(); // S = { 1, 2, .., N } for (int i=0; i < matrix[0].length; i++) { S.add(i); } // For Row i: 1..M for (Integer i = 0; i < matrix.length; i++) { // For Column j in list S for (Integer j : S) { if (matrix[i][j] != 1) { S.remove(j); } } } return S; } public static void main (String [] args) { int [][] matrix = { {1,1,1}, {0,1,1}, {0,0,1}, }; ArrayList<Integer> columns = solve (matrix); System.out.print(" columns that have 1s are: "); for (Integer n : columns) System.out.print(n+" "); } } 

Solution 2: O (n) using a personalized data structure

 private class Column { public ArrayList<Integer> data; public int count; public Column () { data = new ArrayList<Integer>(); count = 0; } public void add (int val) { data.add(val); count += val; } } public class Main { public static void main (String [] args) { Column [] matrix = { new Column (), new Column (), new Column () }; matrix[0].add(1); matrix[0].add(0); matrix[0].add(0); matrix[1].add(1); matrix[1].add(1); matrix[1].add(0); matrix[2].add(1); matrix[2].add(1); matrix[2].add(1); System.out.print(" columns that have 1s are: "); for (Column column : matrix) { if (column.count == column.data.size()) System.out.print(n+" "); } } }