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