Problem:Looking for an efficient algorithm to find the largest value that exists in all columns.Constraints:The values in each column are always decreasingMy algorithm:Check the first row for matchUse the lowest value from first row to search for matchUse the value from row x, column y to search for matchIncrease row index until nIncrease column index until nExamples:Best case$$A=\begin{bmatrix}17 & 17 & 17\\ 14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\end{bmatrix}$$Select Row1,Col1 to match17, 17, 17Result is 17Average case$$B=\begin{bmatrix}13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\\ 9 & 5 & 10\end{bmatrix}$$Select Row1,Col1 to match13, 10, 15Select lowest value in Row1 (10)10, 10, 10Result is 10Worst case$$C=\begin{bmatrix}14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\end{bmatrix}$$Select Row1,Col1 to match14, 14, 16Select lowest value in Row1 (14)14, 14, xSelect Row2,Col1 to match13, x, 13Select Row2,Col2 to match10, 10, xSelect Row2,Col3 to matchx, x, 15Select Row3,Col1 to match11, x, xSelect Row3,Col2 to matchx, 8, xSelect Row3,Col3 to match13, x, 13Select Row4,Col1 to match10, 10, x(repeated!)Select Row4,Col2 to matchx, 7, xSelect Row4,Col3 to matchx, x, 12Result is no matches
Greatest matching values in matrix
algorithms