Young Tableau

Young tableau consists of rows and columns of numbers in the form of a matrix. The special property of young tableau is that its rows and columns are sorted. Young tableau can also function as a min heap. There are different interesting algorithms relating to young tableau.

Example of young tableau.

1 2 3
4 6 7
5 7 12

It's clear from the example that each row and column is sorted.

Here is one interesting problem on Young Tableau: How to find an element in an Young Tableau?

Naive search on the table would require O(mn) time. Where m is the number of rows and n is the number of columns. Can we do bit better? Turns out we can. The trick is to start from the top right corner> if the element we are searching for is greater we move down in the column. If the element we are searching for is smaller we move left in the row. We repeat the procedure until we find the element or we end up in a row or column beyond the table. This would translate to a simple code below:

The example assumes 3 X 3 matrix for simplicity. row is the number of rows and col is the number of columns in the matrix and n is the element being looked for.

int find_n(int x[][3],int row, int col, int n) {

 int r =0 , c = col -1;
 while( r < row && col >=0) {
  if(x[r][c] == n)
   return n;
  else if ( x[r][c] > n)
   c--;
  else
   r++;
 }
 return -1;
}

Another problem in Young Tableau is extracting minimum element. The minimum element is the element in (0,0) position. The main problem is replacing the spot (0,0) after minimum element has been removed. The code is given below (sorry that i have it in Java because I did these two things separately but still i believe it is simple enough so i thought it was not necessary to put both of these in same language)

/*
a is young tableau, i and j are current position in the tableau that we are filling
m and n are number of rows and column
*/
void youngify(int[][] a, int i, int j, int m, int n) {
  if (i > m || j > n)
   return;

  int x = -1, y = -1;

  if (i + 1 < m && a[i + 1][j] < a[i][j]) {
   a[i][j] = a[i + 1][j];
   x = i + 1;
   y = j;

  }
  if (j + 1 < n && a[i][j + 1] < a[i][j]) {
   a[i][j] = a[i][j + 1];
   x = i;
   y = j + 1;
  }

  if (x != -1) {
   //the empty space is filled with marked
   //by maximum value a integer can hold
   a[x][y] = Integer.MAX_VALUE;
   youngify(a, x, y, m, n);
  }

 }

Inserting an element into non full young tableau follows the similar process as extracting minimum element. The idea is to put the element into last row and column and move it upto the position where is should be.

Sorting can also be implemented for n X n young tableau in O(n ^3) time by using the operation by which we extract minimum element. The idea is to extract minimum element which takes O(n+n) = O(n) time, IF we repeat this for n^2 element it will take O (n ^3)time.