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

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
    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
    Skype id: saurabhmaxmunus
    Ph:+91 8553576305 / 080 - 41103383