Monday, July 12, 2010

Amazing youngs tableau

Youngs tableau is a matrix in which the elements are sorted in every row and every column.
every row is increasing sequence from left to right
every column is increasing sequence from top to bottom

Let the matrix be of size N x N .
Do insertion and searching in O(N).

Try doing it yourself. It isn't so hard.......however i have posted the answer below.

The tableau behaves as a heap from one corner and BST from another corner.

Lets name the matrix A of size N x N
Take any element A[i][j]
1. A[i][j] < A[t][j] for t = i+1 ....... N
2. A[i][j] < A[i][t] for t = j+1 ....... N
3. A[i+1][j] and A[i][j+1] can be thought of as childs of A[i][j]
thus above structure resembles a heap

similarly from upper right corner the matrix looks like a BST

do insert operation in BST --> O(n) in this case
do search operation in HEAP --> O(n) in this case

No comments:

Post a Comment