CODEWITHSUNDEEP
arraysalgorithmmatrixsearchboolean
Bob
Bob

Reputation: 31

Matrix has a column with all 'true'. How to find it in less than O(mn) time?

I have a 2D array of true/false values. I know that it has some column with all values true, and I know that it has some row with all values false except where it intersects that column. For example:

    0 1 2 3
  +--------
0 | N Y Y Y
1 | N Y Y Y
2 | N Y Y Y
3 | N N Y N
4 | N Y Y Y

I want to find the column with all values true. Is there a way to do that in less than O(mn) time?

Upvotes: 2

Views: 131

Answers (1)

ruakh
ruakh

Reputation: 183290

Let's call the column with all Y's the "special" column, and likewise for the first row with one Y and the rest N's.

Start at top left. Whenever you see an N, you know this isn't the special column, so move right. Whenever you see a Y, you know that either this is the special column, or it's not the special row, so move down. When you make it all the way to a Y at the bottom, you must have passed through the special row, so you know that you must be in the special column (because only the special column can get you through the special row, and once you're on the special column you'll never move off of it).

This takes O(m+n) time, because you move right at most n−1 times and move down at most m−1 times.

Upvotes: 8

Related Questions