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