Young Tableau | Insert, Search, Extract-Min, Delete, Replace

A M x N Young tableau is an M x N matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be infinity, which indicates an empty entry. Thus, a Young tableau can be used to hold n <= N2 finite numbers.


 

For example, following matrix is a Young tableau:

Young tableau

 
In this post, we will see how to

 

1. Insert operation in Young tableau

 

To insert an element into non-full Young tableau, the idea is to place the element at bottom-right corner of the tableau and then move it upwards and leftwards to its correct position within the tableau. This is demonstrated below in C++:

 

Download   Run Code

Output:

10 11 12 15
16 18 20 22
25 27 30 34
35 40 44 45

 
The time complexity for the insert operation is O(M + N) while the overall time complexity to construct a M x N Young tableau from given list of elements is O(M*N*(M + N)). The auxiliary space used by the program is O(M + N) for call stack.

 

2. Search operation in Young tableau

 

Naive solution is to traverse the complete tableau to search for the given value. The problem with this approach is that it would require O(M * N) time for searching in a M x N Young tableau.

Can we do better?

The idea is to take advantage of the fact that a Young tableau is row-wise and column-wise sorted matrix. We start from the top-rightmost corner of the tableau and compare the current element with the one we’re looking for and accordingly move left or down:

  1. If current element is less than the key, we increment row index (move to the next row)
     
  2. If current element is more than the key, we decrement column index (move to the previous column)
     
  3. If current element is equal to the key, we return true as we have found the element. If we end up in a row or column beyond the tableau boundary, we terminate the search and return false.

 
The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

Key 20 found in tableau
Key 25 found in tableau

 
Time complexity of search operation is O(M + N) and auxiliary space used by the program is O(1).

 

3. Extract-Min operation in Young tableau

 

The minimum element is present at the position (0,0) in tableau. To remove an element (i,j) from a tableau, we simply replace the cell value by infinity and return the element. This causes the Young tableau to become unstable and the sub-matrix formed by (i, j), (i, N-1), (M-1, j), and (M-1, N-1) voilates the Young tableau property (the sub-matrix is not row-wise sorted and column-wise sorted anymore).

Young tableau is similar to a heap where each cell (i,j) can be considered as the root node. The bottom cell (i+1,j) and right cell (i,j+1) of a cell (i,j) can be considered as the left and right child of the root node.

The idea is to perform a procedure similar to HEAPIFY-DOWN to restore the Young tableau property. If (i,j) is larger than its neighbors, we swap the smaller of (i+1,j) and (i,j+1) with (i,j). This restores the tableau property for cell (i,j) but reduces the problem for cell (i+1,j) or cell (i,j+1).

The algorithm can be implemented recursively as follows in C++-

 

Download   Run Code

Output:

10 11 12 15 16 18 20 22 25 27 30 34 35 40 44 45

 
The fixTableau() routine takes a M x N matrix and breaks it into either a (M-1) x N or a M x (N-1) matrix. So, the recurrence relation is:

T(M, N) = T(M-1, N) + T(M, N-1)

So the overall time complexity of Extract-Min operation on a Young tableau is O(M + N).

 

4. Delete operation in Young tableau

 

The idea is very simple and inspired from Extract-Min operation on the Young tableau. To delete an element present at cell (i, j), make it as infinity and then fix the young tableau property of sub-matrix formed by (i, j), (i, N-1), (M-1, j), and (M-1, N-1).

 
The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

10 12 15 16
11 18 25 35
22 27 30 45
34 40 44 2147483647

 
The time complexity of delete operation is O(M + N) and auxiliary space used by the program is O(M + N) for call stack.

 

5. Replace operation in Young tableau

 

To replace an element x with the element y in a Young tableau, we start by searching x‘s position (i, j) in the tableau. Then we replace the element at cell (i, j) by infinity, and fix the young tableau property. Finally, we place the element y at the bottom right corner of the tableau and move the key to its correct position in the tableau.

 
The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

10 12 14 15
11 16 18 25
22 27 30 35
34 40 44 45

 
The time complexity of replace operation is O(M + N) and the auxiliary space used by the program is O(M + N) for call stack.

 
Exercise: Determine if a given matrix is Young Tableau or not i.e. check if the matrix is row wise and column wise sorted.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of