Monday, July 12, 2010

Amazing youngs tableau

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

1 comment:

  1. 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
    MaxMunus 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/


    ReplyDelete