Greatest matching values in matrix

Question

Problem:

Looking for an efficient algorithm to find the largest value that exists in all columns.

---

Constraints:

• The values in each column are always decreasing

---

My algorithm:

1. Check the first row for match
2. Use the lowest value from first row to search for match
3. Use the value from row x, column y to search for match
4. Increase row index until n
5. Increase column index until n

---

Examples:

Best case $$A=\begin{bmatrix}17 & 17 & 17\\ 14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\end{bmatrix}$$

Select Row1,Col1 to match
17, 17, 17

Result is 17

Average case $$B=\begin{bmatrix}13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\\ 9 & 5 & 10\end{bmatrix}$$

Select Row1,Col1 to match
13, 10, 15

Select lowest value in Row1 (10)
10, 10, 10

Result is 10

Worst case $$C=\begin{bmatrix}14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\end{bmatrix}$$

Select Row1,Col1 to match
14, 14, 16

Select lowest value in Row1 (14)
14, 14, x

Select Row2,Col1 to match
13, x, 13

Select Row2,Col2 to match
10, 10, x

Select Row2,Col3 to match
x, x, 15

Select Row3,Col1 to match
11, x, x

Select Row3,Col2 to match
x, 8, x

Select Row3,Col3 to match
13, x, 13

Select Row4,Col1 to match
10, 10, x
(repeated!)

Select Row4,Col2 to match
x, 7, x

Select Row4,Col3 to match
x, x, 12

Result is no matches

Answer 1

Build single hash table from any column and augment it with counter, set it to 1.
Add second column to the hash table discarding not existing values from the second column. Optionally you can remove values that are still singular.
Add third column element by element, store the maximal encountered triplet.

This will run in expected $\mathcal O(n)$ time, where $n$ is column length.

What you have proposed looks a bit like selection sort. Making it explicit, sort columns in descending order and start checking for triplet. It would give $\mathcal O(n\log(n))$ runtime.