TITLE: $k$-th number in $N \times M$ Table
QUESTION [6 upvotes]: Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq  i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in increasing value ?

REPLY [0 votes]: This is basically selection in a Young's tableaux, and also selection in X+Y sorted SUM matrix (taking $X[i] = Y[i] = \log i$, the sums being $S[i,j] = \log i + \log j$), the latter of which has known $O(M+N)$ time algorithms for selecting the $k^{th}$ largest element.
This paper: Generalize Selection and Ranking: Sorted Matrices has an $O(M+N)$ time algorithm for sorted sums selection.
An explanation of that algorithm (called the FJ-Algorithm, for the initials of the authors of the above paper) can be found in section 2 of this paper: Cache oblivious selection in sorted X+Y matrices.
{"set_name": "stack_exchange", "score": 6, "question_id": 869974}