# Solved: Young Tableau Problem in Cormen using Java and C++

Table of Contents

In this article, we will see how to solve the famous Young Tableau problem given in Cormen using Java and C++ code. Young Tableau is a very popular problem in the world of Data Structure and Algorithms to deal with. It was first introduced by a mathematician Alfred Young in the year 1900. It provides a very convenient way to describe the group representations of the symmetric and general linear groups. Here we will try to understand this theory and know how to perform different operations using Java and C++ code examples. So without further delay, let's begin !!

## Solved: Young Tableau Problem in Cormen using Java and C++

An `M × N` Young tableau is an `M × N` matrix such that the entries of each row are sorted from left to right and the entries of each column are sorted from top to bottom. Some of the young tableau entries may be infinity(`INT_MAX` in cpp and `Integer.MAX_VALUE` in Java), which we treat as non-existent elements. Thus young tableau can hold n <= M*N finite numbers.

Young Tableau is similar to min heap except the condition that in min heap we only deal with `1D array` and in Young Tableau we deal with `2D Array`.

## Insert Operation

To insert new element into Young Tableau (Non Full Young Tableau), we place the new element at bottom right corner and then move that element to its correct position upwards and leftward with following procedure:-

a) If the current element `(i, j)` is smaller than the `(i-1, j)` element then we will swap both element.

b) If the current element `(i, j)` is smaller than the `(i, j-1)` element then we will swap both element.

c) In this way we will get the `(i, j)` greater than both `(i-1, j)` and `(i, j-1)` and the newly inserted element will be put at its correct position.

The Time complexity of inserting a new element in Young Tableau is `O(M + N)`.

## Extract Minimum Operation

The minimum element of Young Tableau is present at `(0,0)` cell. We can easily access that and print that element in `O(1)` time.

## Search Operation

A naive way to search the key in the Young tableau is to go through each element and check whether given element is present or not, but the time complexity in this case will be `O(M x N)`. We can solve this problem with better time complexity of `O(M + N)`. We will use the fact the each row is sorted from left to right and each column is sorted from top to bottom.

a) We will start our search from top right corner of matrix `(0, N-1)` cell.

b) If the key is equal to current element that means key is present in the matrix.

c) If the key is smaller than the current element we will decrement the column index by one(move left).

d) If the key is greater than the current element we will increment the row number by one (move down).

We will repeat this process until the row index and column index are not out of bound.

## Delete Operation

To delete the given element from Young Tableau we replace that element with infinity. But due to this the sorted arrangement of given row and column get disturbed and now we will need to rearrange the matrix elements. We will move the infinity towards right and bottom with following procedure:-

a) If the current element `(i, j )` is smaller than the `(i-1, j)` element then we will swap both element.

b) If the current element `(i, j)` is smaller than the `(i, j-1)` element then we will swap both element.

c) In this way we will get the `(i, j)` greater than both `(i-1, j)` and `(i, j-1)` and the newly inserted element will be put at its correct position.

The Time complexity of Delete operation in Young Tableau is `O(M + N)`.

## Java Code

```import java.io.*;

class GFG {
public static void swap(int[][]tableau,int row1,int col1,int row2,int col2)
{
int a=tableau[row1][col1];
tableau[row1][col1]=tableau[row2][col2];
tableau[row2][col2]=a;
}

public static void util(int[][] tableau, int row, int col)
{
//base condition
if (row == 0 && col == 0) {
return;
}

// handle first row specially as there is no above element for this row
if (row == 0)
{
if (tableau[row][col] < tableau[row][col-1])
{
swap(tableau,row,col,row,col-1);
util(tableau, row, col - 1);
}
return;
}

// handle first column separately as there is no left column
if (col == 0)
{
if (tableau[row][col] < tableau[row-1][col])
{
swap(tableau,row,col,row-1,col);
util(tableau, row - 1, col);
}
return;
}
//go up
if (tableau[row][col] < tableau[row-1][col])
{
swap(tableau,row,col,row-1,col);
util(tableau, row - 1, col);
}
//go left
if (tableau[row][col] < tableau[row][col-1])
{
swap(tableau,row,col,row,col-1);
util(tableau, row, col - 1);
}
}

public static void insert(int[][] tableau,int key){
int M=tableau.length;
int N=tableau[0].length;
if(tableau[M-1][N-1]!=Integer.MAX_VALUE){
System.out.println("Can not insert new element as tableau is already full");
return;
}
tableau[M-1][N-1]=key;
util(tableau,M-1,N-1);
}

public static void search(int[][] tableau,int key){
int i=0;
int j=tableau[0].length-1;
while(i<tableau.length && j>=0){
if(tableau[i][j]==key){
System.out.print("the given key is found at "+i+"th row and "+j+"th column \n");
return;
}else if(key>tableau[i][j]){
i++;
}else{
j--;
}
}
System.out.println("given key is not present inside young tableau");
}

public static void extractMin(int[][] tableau){
System.out.print("Minimum element in young tableau is "+ tableau[0][0]+"\n");
}

public static void makeTableau(int[][] tableau, int row, int col){
//M x N Young tableau
int M=tableau.length;
int N=tableau[0].length;

// get the values present at the bottom and right cell of the current cell
int bottom = (row + 1 < M) ? tableau[row + 1][col] : Integer.MAX_VALUE;
int right = (col + 1 < N) ? tableau[row][col + 1] : Integer.MAX_VALUE;

if (bottom == Integer.MAX_VALUE && right == Integer.MAX_VALUE) {
return;
}
if(bottom < right) // go down
{
swap(tableau,row,col,row+1,col);
makeTableau(tableau,row+1,col);
}
else // go right
{
swap(tableau,row,col,row,col+1);
makeTableau(tableau,row,col+1);
}

}

public static void deleteElement(int[][] tableau,int row,int col){
//base case
if(row >= tableau.length || col>= tableau[0].length){
return;
}
//to delete the elementat (i,j) make it as infinity
tableau[row][col]=Integer.MAX_VALUE;

//fix the young tableau property
makeTableau(tableau,row,col);
}

public static void printTableau(int[][] tableau){
for(int i=0;i<tableau.length;i++){
for(int j=0;j<tableau[i].length;j++){
System.out.print(tableau[i][j] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {
int[][] tableau = {{10,15,35},{20,30,40},{45,50,Integer.MAX_VALUE}};
printTableau(tableau);
insert(tableau,12);
printTableau(tableau);
search(tableau,40);
extractMin(tableau);
deleteElement(tableau,1,0);
printTableau(tableau);
}
}```

## C++ Code

```#include <bits/stdc++.h>
using namespace std;

void util(vector<vector<int>> &tableau, int row, int col)
{
//base condition
if (row == 0 && col == 0) {
return;
}

// handle first row specially as there is no above element for this row
if (row == 0)
{
if (tableau[row][col] < tableau[row][col-1])
{
swap(tableau[row][col], tableau[row][col-1]);
util(tableau, row, col - 1);
}
return;
}

// handle first column seperately as there is no left column
if (col == 0)
{
if (tableau[row][col] < tableau[row-1][col])
{
swap(tableau[row][col], tableau[row-1][col]);
util(tableau, row - 1, col);
}
return;
}

//go up
if (tableau[row][col] < tableau[row-1][col])
{
swap(tableau[row][col], tableau[row-1][col]);
util(tableau, row - 1, col);
}

//go left
if (tableau[row][col] < tableau[row][col-1])
{
swap(tableau[row][col], tableau[row][col-1]);
util(tableau, row, col - 1);
}
}

void insert(vector<vector<int>>&tableau,int key){
int M=tableau.size();
int N=tableau[0].size();
if(tableau[M-1][N-1]!=INT_MAX){
cout<<"Can not insert new element as tableau is already full"<<endl;
return;
}
tableau[M-1][N-1]=key;
util(tableau,M-1,N-1);
}

void search(vector<vector<int>>tableau,int key){
int i=0;
int j=tableau[0].size()-1;
while(i<tableau.size() && j>=0){
if(tableau[i][j]==key){
cout<<"the given key is found at"<<i<<"th row and"<<j<<"th column"<<endl;
return;
}else if(key>tableau[i][j]){
i++;
}else{
j--;
}
}
cout<<"given key is not present inside young tableau"<<endl;
}

void extractMin(vector<vector<int>>tableau){
cout<<"Minimum element in young tableau is: "<<tableau[0][0]<<endl;
}

void makeTableau(vector<vector<int>> &tableau, int row, int col)
{
// M × N Young tableau
int M = tableau.size();
int N = tableau[0].size();

// get the values present at the bottom and right cell of the current cell
int bottom = (row + 1 < M) ? tableau[row + 1][col] : INT_MAX;
int right = (col + 1 < N) ? tableau[row][col + 1] : INT_MAX;

if (bottom == INT_MAX && right == INT_MAX) {
return;
}

if (bottom < right) // go down
{
swap(tableau[row][col], tableau[row + 1][col]);
makeTableau(tableau, row + 1, col);
}
else // go right
{
swap(tableau[row][col], tableau[row][col + 1]);
makeTableau(tableau, row, col + 1);
}
}

void deleteElement(vector<vector<int>>&tableau, int row, int col){
// base case
if (row >= tableau.size() || col >= tableau[0].size()) {
return;
}
// to delete the element at `(i, j)`, make it as infinity
tableau[row][col] = INT_MAX;

// fix the Young tableau property
makeTableau(tableau, row, col);
}

void printTableau(vector<vector<int>> tableau){
for(int i=0;i<tableau.size();i++){
for(int j=0;j<tableau[0].size();j++){
cout<< tableau[i][j]<<" ";
}
cout<<endl;
}
}

int main() {
vector<vector<int>>tableau={{10,15,35},{20,30,40},{45,50,INT_MAX}};
printTableau(tableau);
insert(tableau,12);
printTableau(tableau);
search(tableau,40);
extractMin(tableau);
deleteElement(tableau,1,0);
printTableau(tableau);
}```

## Conclusion

In this article we have gone through what is young tableau and the different operations in young tableau like insert operation, search operation, extract minimum operation and delete operation. We also saw time complexity of each operation and at last we implemented all the above features in java and C++.

error: Content is protected !!