Most efficient method to query a Young Tableau
- by Matthieu M.
A Young Tableau is a 2D matrix A of dimensions M*N such that:
i,j in [0,M)x[0,N):
for each p in (i,M), A[i,j] <= A[p,j]
for each q in (j,N), A[i,j] <= A[i,q]
That is, it's sorted row-wise and column-wise. Since it may contain less than M*N numbers, the bottom-right values might be represented either as missing or using (in algorithm theory) infinity to denote their absence.
Now the (elementary) question: how to check if a given number is contained in the Young Tableau ?
Well, it's trivial to produce an algorithm in O(M*N) time of course, but what's interesting is that it is very easy to provide an algorithm in O(M+N) time:
Bottom-Left search:
Let x be the number we look for, initialize i,j as M-1, 0 (bottom left corner)
If x == A[i,j], return true
If x < A[i,j], then if i is 0, return false else decrement i and go to 2.
Else, if j is N-1, return false else increment j
This algorithm does not make more than M+N moves. The correctness is left as an exercise.
It is possible though to obtain a better asymptotic runtime.
Pivot Search:
Let x be the number we look for, initialize i,j as floor(M/2), floor(N/2)
If x == A[i,j], return true
If x < A[i,j], search (recursively) in A[0:i-1, 0:j-1], A[i:M-1, 0:j-1] and A[0:i-1, j:N-1]
Else search (recursively) in A[i+1:M-1, 0:j], A[i+1:M-1, j+1:N-1] and A[0:i, j+1:N-1]
This algorithm proceed by discarding one of the 4 quadrants at each iteration and running recursively on the 3 left (divide and conquer), the master theorem yields a complexity of O((N+M)**(log 3 / log 4)) which is better asymptotically.
However, this is only a big-O estimation...
So, here are the questions:
Do you know (or can think of) an algorithm with a better asymptotical runtime ?
Like introsort prove, sometimes it's worth switching algorithms depending on the input size or input topology... do you think it would be possible here ?
For 2., I am notably thinking that for small size inputs, the bottom-left search should be faster because of its O(1) space requirement / lower constant term.
