Extract Min of Young Tableau In Java

In this tutorial, we are going to shed light on how to extract the minimum value from a young tableau in Java.

First, we will start with a little bit of background on what a Young Tableau is. Then, we will see in practice how to implement extracting the min element.

What is Young Tableau?

In short, Young tableau is a matrix of M rows on N columns where:

• The entries of each row are sorted from left to right

• The entries of each column are sorted from top to bottom

Some of the entries can hold INFINITY (∞) as a value to denote an empty entry. Typically, a Young tableau can hold a number of elements less than or equal to MxN.

Now that we know what a Young tableau is, let’s see how we can extract its min element.

Extract Minimum Value

Basically, the min element is present at position (0, 0) since the entries are already sorted from left to right and from top to bottom.

The basic idea here is to return the element at position (0, 0) and delete it. However, we will need to do some swapping and sorting operations to make the new matrix a young tableau again.

So, let’s see this in practice:

    
        public static int extractMin(int[][] youngTableau) {
            // Extract the min element
            int minItem = youngTableau[0][0];
            // Replace it with Integer.MAX_VALUE
            youngTableau[0][0] = Integer.MAX_VALUE;
            // Adjust the newmatrix
            adjust(youngTableau, 0, 0);
            // Return the extracted element
            return minItem;
        }
    

As we can see, first we get the element at position [0][0]. Then, we replace it with Integer.MAX_VALUE which is the maximum value an int.

Lastly, we call the adjust() method to make sure that the result of the extraction honors Young tableau principles.

So, let’s see how adjust() is implemented:

    
        public static void adjust(int[][] youngTableau, int firstIndex, int secondIndex) {
            int m = youngTableau.length;
            int n = youngTableau[0].length;
            int tmpFirstIndex = firstIndex;
            int tmpSecondIndex = secondIndex;
            if (firstIndex + 1 < m) {
                if (youngTableau[firstIndex][secondIndex] > youngTableau[firstIndex + 1][secondIndex]) {
                    tmpFirstIndex = firstIndex + 1;
                    tmpSecondIndex = secondIndex;
                }
            }
            if (secondIndex + 1 < n) {
                if (youngTableau[tmpFirstIndex][tmpSecondIndex] > youngTableau[firstIndex][secondIndex + 1]) {
                    tmpFirstIndex = firstIndex;
                    tmpSecondIndex = secondIndex + 1;
                }
            }
            int tmpItem;
            if (tmpFirstIndex != firstIndex || tmpSecondIndex != secondIndex) {
                tmpItem = youngTableau[tmpFirstIndex][tmpSecondIndex];
                youngTableau[tmpFirstIndex][tmpSecondIndex] = youngTableau[firstIndex][secondIndex];
                youngTableau[firstIndex][secondIndex] = tmpItem;
                adjust(youngTableau, tmpFirstIndex, tmpSecondIndex);
            }
        }
    

As we mentioned earlier, the purpose of the adjust() method is to restore the Young tableau after extracting the min element.

Now that we put all the pieces together, let’s test our min extraction implementation:

    
        public static void main(String[] args) {
            int[][] youngTableau = { 
                    { 5, 8, 20, 90, 300 }, 
                    { 6, 11, 28, 101, 400 }, 
                    { 12, 36, 38, 203, 500 }, 
                    { 55, 60, 71, 302, 600 } 
            };
            System.out.println("Displaying Young Tableau before the min extraction operation");
            display(youngTableau);
            int extractedMinItem = extractMin(youngTableau);
            System.out.println("The extracted minimum is:" + extractedMinItem);
            System.out.println("Displaying Young Tableau after extracting the min element");
            display(youngTableau);
        }
    

Running the above program will produce:

Conclusion

To summarize it all, in this short article, we explained in detail what a Young tableau is.

Along the way, we saw together how to extract the minimum value from it.