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

I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in ALTERYX, kindly contact us http://www.maxmunus.com/contact

ReplyDeleteMaxMunus Offer World Class Virtual Instructor led training on ALTERYX. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.

For Demo Contact us.

Saurabh Srivastava

MaxMunus

E-mail: saurabh@maxmunus.com

Skype id: saurabhmaxmunus

Ph:+91 8553576305 / 080 - 41103383

http://www.maxmunus.com/