Youngs tableau is a matrix in which the elements are sorted in every row and every column.

http://en.wikipedia.org/wiki/Young_tableau

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.

Hint:

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

Answer:

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