The algorithmic solution to this was asked as a question in GATE 1996

52 votes

A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique entries.

$$\begin{array}{|l|l|l|l|}\hline \textbf{1} & \text{2}& \text{5} & \text{14} \\\hline \text{3} & \text{4} & \text{6} & \text{23} \\\hline \text{10} & \text{12} & \text{18} & \text{25} \\\hline \text{31} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} \\\hline \end{array}$$

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled with a $\infty$). The minimum number of entries (other than $1$) to be shifted, to remove $1$ from the given Young tableau is _____.

$$\begin{array}{|l|l|l|l|}\hline \textbf{1} & \text{2}& \text{5} & \text{14} \\\hline \text{3} & \text{4} & \text{6} & \text{23} \\\hline \text{10} & \text{12} & \text{18} & \text{25} \\\hline \text{31} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} \\\hline \end{array}$$

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled with a $\infty$). The minimum number of entries (other than $1$) to be shifted, to remove $1$ from the given Young tableau is _____.

61 votes

Best answer

The answer should be $5$.

- We first need to shift $2$ in place of $1$ keeping $5$ AND $14$ intact as it isn't mentioned in the question that the entire row elements move.
- $4$ is shifted up,next to $2$ (keeping $12$ and infinity intact in column $2$).
- Now in second row $6$ is shifted left.
- $18$ shifts up to the second row
- And finally $25$ is shifted left to the third column.

So, this takes $5$ moves and still maintains the tableau property. Also infinity is placed to the right of $25$ and below $23$ (unfilled entries to be filled with $\infty$ ). The final table would look as follows.

$$\begin{array}{|l|l|l|l|}\hline \text{2} & \text{4}& \text{5} & \text{14} \\\hline \text{3} & \text{6} & \text{18} & \text{23} \\\hline \text{10} & \text{12} & \text{25} & \infty \\\hline \text{31} & \text{$\infty$} & \text{$\infty$} & \text{$\infty$} \\\hline \end{array}$$

79

Once an entry a[i][j] is moved then min(a[i+1][j], a[i][j+1]) will take that position, and this goes on.

1 is removed, min (2,3) = 2. 2 takes 1's position

Now 2 is removed, min (4,5) will take its position.

We do this till we reach to the end.

1 is removed, min (2,3) = 2. 2 takes 1's position

Now 2 is removed, min (4,5) will take its position.

We do this till we reach to the end.

0

3 shifted upwards in place of 1 10 shifted upwards in place of 3 31 shifted upwards in place of 10 3 2 5 14 10 4 6 23 31 12 18 25 ∞ ∞ ∞ ∞

So, according to me there are minimum 3 shifts. Please advise what is wrong with this approach

11 votes

Answer is 5.

And shifts are,

Shift 1 - 2- left

Shift 2- 4-up

Shift 3- 6 - left

Shift 4- 18-up

Shift 5- 25 left

1

only your answer is solved according to the question specifications with exact approach in a detailed manner.

5

same thing occurred to me when i first attempted this question

after some thinking i noticed some similarities to concept of heap ,

here 1 is like the root of heap and elts. on row a[i][j+1] > a[i][j] and also along col a[i+1][j]>a[i][j]

suggesting them to be looked upon as the left and right child of heap ,then every elt has heap property

the difference from heap would be that elts of left and right sub-tree can be shared also which is not the case with heap ,Also the shifting procedure sounds very similar to how we fix heap after removing elt

So if you model this structure as similar to heap and try to move elts. keeping fix heap in back of your mind and use ideas from it like comparing left and right children and moving smaller one above

So i think in that sense it is a great question as they wanted to check if (i) we can identify the similarity with heap and (ii) apply heap algorithms in this new setting

Unfortunately a kind of ad-hoc approach also works somewhat on the lines of hit and trail which most people did and got two marks and the beauty of this question could never be realized.

after some thinking i noticed some similarities to concept of heap ,

here 1 is like the root of heap and elts. on row a[i][j+1] > a[i][j] and also along col a[i+1][j]>a[i][j]

suggesting them to be looked upon as the left and right child of heap ,then every elt has heap property

the difference from heap would be that elts of left and right sub-tree can be shared also which is not the case with heap ,Also the shifting procedure sounds very similar to how we fix heap after removing elt

So if you model this structure as similar to heap and try to move elts. keeping fix heap in back of your mind and use ideas from it like comparing left and right children and moving smaller one above

So i think in that sense it is a great question as they wanted to check if (i) we can identify the similarity with heap and (ii) apply heap algorithms in this new setting

Unfortunately a kind of ad-hoc approach also works somewhat on the lines of hit and trail which most people did and got two marks and the beauty of this question could never be realized.

6 votes

Actually, the element deleted is replaced by by infinity in that cell of the Young Tableau. And, then we perform an operation called Youngify(Y, i, j) where Y is the 2D-Young matrix, i and j are the coordinates of the element deleted.

This function sets the blank/infinity created by the deletion of the element in its proper position by rearranging the Young Tableau much like the heapify procedure.

Please refer this PDF which contains the details - https://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf

The blank/infinity is compared with the immediate right and immediate bottom element each time and the smallest is exchanged with it out of the 2. This procedure ultimately arranges all the elements in their correct position.

Eg :- Youngify on position Y[1, 1] :- The position Y[1, 1] = INF, is compared with position Y[1, 2] = 2 and position Y[2, 1] = 3, the smaller one is Y[1, 2] is exchanged with Y[1, 1] and now Y[1, 2] becomes INF. Now same procedure is repeated for Y[1, 2] and so on..

2 4 5 14

3 6 18 23

10 12 25 oo

31 oo oo oo

3 votes

sir may i think this Young tableau as min heap.. delete 1 and it should filled by 31.. then just apply modified heapify procedure to get desired Young tableau..

removal of 1 and replacement of 1s position with 31 is single atomic operations so shift should not be counted..

later only swaps (modified heapify) required..

31 with 2,

31 with 4,

31 with 6,

31 with 18,

31 with 25..

is it not right way ???

removal of 1 and replacement of 1s position with 31 is single atomic operations so shift should not be counted..

later only swaps (modified heapify) required..

31 with 2,

31 with 4,

31 with 6,

31 with 18,

31 with 25..

is it not right way ???

2 votes

Ans is 5, shift 2,5,14 to left and 23,25 up.

Edit: these shift moves will violate the Young Table property, So we have to shift 2,4,6,18 and 25 in zig-zag fashion.

Edit: these shift moves will violate the Young Table property, So we have to shift 2,4,6,18 and 25 in zig-zag fashion.

2

@Vikrant Singh: The shifts you make will give the following matrix:

2 | 5 | 14 | 23 |

3 | 4 | 6 | 25 |

10 | 12 | 18 | ∞ |

31 | ∞ | ∞ | ∞ |

3

infinity too should be shifted, right?

The table I posted in the comments? No. the entries marked in red violate the given constraints. 5>4 and 14 > 6

The table I posted in the comments? No. the entries marked in red violate the given constraints. 5>4 and 14 > 6

1

I missed that too. But as per the question we needn't shift infinity. Once an element is shifted that entry becomes infinity.

1

Once an element is shifted that entry becomes infinity.

hmm.. No?

Because then, when we shift $2$, the cell $(0,1)$ will be filled with $\infty$, and we would be swapping (not shifting) the entries after that.

IMO, the shifting will be done as long as something can be shifted into an empty cell.

Once that becomes impossible (like hitting the bottom right cell), the empty entry will be filled with $\infty$.

So, the shift of infinity from $(3,3)$ to $(2,3)$ must be counted, and then the cell $(3,3)$ is filled with $\infty$

1

@Pragy Agarwal Shouldn't algorithm stop shifting once it has encountered an infinity. Because after that, all shifting will be of infinity elements only. Once it is clear that only infinty element can be shifted in empty cell, just fill that cell with infinity and stop. This method because it's been asked to minimize the shifting of elements.

2 votes

2 votes

A Young Tableau is a matrix, such that each row, as well as each column is sorted in ascending order,

The most optimal solution to rearrangement in this grid-like structure is to move in a zig-zag manner,as shown.

**5** is the answer.

1 vote

After removing 1

NULL | 2 | 5 | 14 |

3 | 4 | 6 | 23 |

10 | 12 | 18 | 25 |

31 | Infinite | Infinite | Infinite |

NULL moves right:

(Note: NULL cannot move down because it will contradict the given question conditions. Hence, we have to move right.)

2 | NULL | 5 | 14 |

3 | 4 | 6 | 23 |

10 | 12 | 18 | 25 |

31 | Infinite | Infinite | Infinite |

NULL moves down:

2 | 4 | 5 | 14 |

3 | NULL | 6 | 23 |

10 | 12 | 18 | 25 |

31 | Infinite | Infinite | Infinite |

NULL moves right:

2 | 4 | 5 | 14 |

3 | 6 | NULL | 23 |

10 | 12 | 18 | 25 |

31 | Infinite | Infinite | Infinite |

NULL moves down:

2 | 4 | 5 | 14 |

3 | 6 | 18 | 23 |

10 | 12 | NULL | 25 |

31 | Infinite | Infinite | Infinite |

NULL moves right:

2 | 4 | 5 | 14 |

3 | 6 | 18 | 23 |

10 | 12 | 25 | NULL |

31 | Infinite | Infinite | Infinite |

Now in question given that " Unfilled entries are filled with infinite

Therefore:

2 | 4 | 5 | 14 |

3 | 6 | 18 | 23 |

10 | 12 | 25 | Infinite |

31 | Infinite | Infinite | Infinite |

We will not bring NULL to the bottom right because question is asked to find the minimum.

Since total 5 movements of NULL is involved:

**The answer will be 5**