Algorithm: how to find a column in matrix filled w

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

What is the input for the matrix?

If you get a number for each column, i.e. in your example (in decimal) 14, 8, 4, 31, 1, you could just create a 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 2

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 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.

Answer 4

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 5

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

This solution is written in Java:

Solution 1: O(n^2) straight-forward

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 customized 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+" ");
        }
    }
}