# GATE2015-2-31

4.7k views
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 _____.
in DS
edited
9

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

https://gateoverflow.in/2766/gate1996-14

1
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.

The answer should be $5$.

1. 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.
2. $4$ is shifted up,next to $2$ (keeping $12$ and infinity intact in column $2$).
3. Now in second row $6$ is shifted left.
4. $18$ shifts up to the second row
5. 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}$$

edited
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.
0
Clean solution
0
superb question :)
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

1

Your solution is not following condition mentioned in question. In ur table a[1][1] > a[1][2] which is incorrect

3
what a great technique sachin sir,,,
0
Since it is an 2-D array of integers and in the memory they are contiguous so after shifting 25 why 31 is not shifted instead infinity is placed and also ACC to question there should be no entry to the right of infinity and still 31 is placed ,can anyone explain?

And shifts are,

Shift 1 -  2- left

Shift 2-  4-up

Shift 3- 6 - left

Shift 4-  18-up

Shift 5-  25 left

0
Wondering what concept of computer science , they are wishing to test through this question
1
only your answer is solved according to the question specifications with exact approach in a detailed manner.
0
Thanks @sal
1
@dev will explained.
2
solve using GREEDY method

shift unfilled entry (∞) with min of (right entry , below entry )
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.

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.

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

0
@ravi , so final answer is 5 right ??
0
This will give the result but do we hav to maintain property at each step that nothing is to the right and below 00
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 ???
0
I think ,In question movements are allowed not the jumps .So we cannot  put 31 directly in place of 1.
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.

edited
1
2 left, 4 up, 6 left, 18 up, won't do?
1
@Arjun sir: 25 and $\infty$ too must be shifted left after shifting 18.
2

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

 2 5 14 23 3 4 6 25 10 12 18 ∞ 31 ∞ ∞ ∞
0
missed 25 :( . But the above table is fine rt?
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
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

"unfilled entries may be filled with an infinity"

So, we have a choice here :)

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.
1

@Arjun sir with m rows and n column.

time complexity to delete smallest  element is O(m+n)

time complexity to delete largest  element is O(m+n)

time complexity to delete element is O(m+n) ryt?

Shift $2,4,6,18,25, \infty$ in a zig-zag manner.

 2 4 5 14 3 6 18 23 10 12 25 ∞ 31 ∞ ∞ ∞

edited
0

I don't think we need to count shift. we just have to fill the unfilled entries.

–1
there cannot be any entry to the right of, or below a ∞..
entry 31   violate this condition..
der is  infinity after 25..
correct me ..
0
How is 31 below $\infty$? Are you talking about the $\infty$ on the extreme right?

Well, the question means that within a row, nothing must be to the right of an $\infty$, and in a column nothing must be below an $\infty$.

Since there is no $\infty$ before 31 in the first column, it's all fine.

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.

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:

## Related questions

1
4.8k views
With reference to the B+ tree index of order $1$ shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query. "Get all records with a search key greater than or equal to $7$ and less than $15$ " is ______.
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.