Greatest matching values in matrix 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:


Check the first row for match
Use the lowest value from first row to search for match
Use the value from row x, column y to search for match
Increase row index until n
Increase column index until n




Examples:

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

Select Row1,Col1 to match
17, 17, 17

Result is 17


Average case
$$B=\begin{bmatrix}13 &amp; 10 &amp; 15\\ 11 &amp; 8 &amp; 13\\ 10 &amp; 7 &amp; 12\\ 9 &amp; 5 &amp; 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 &amp; 14 &amp; 16\\ 13 &amp; 10 &amp; 15\\ 11 &amp; 8 &amp; 13\\ 10 &amp; 7 &amp; 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
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.