71 votes 71 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 _____. DS gatecse-2015-set2 databases array normal numerical-answers + – go_editor asked Feb 12, 2015 edited Apr 13, 2019 by Pooja Khatri go_editor 13.0k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Ayush Upadhyaya commented Dec 14, 2017 reply Follow Share The algorithmic solution to this was asked as a question in GATE 1996 https://gateoverflow.in/2766/gate1996-14 19 votes 19 votes smsubham commented Mar 7, 2020 reply Follow Share 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. Source: comments below. 5 votes 5 votes Jaideep Singh commented Dec 3, 2022 reply Follow Share smsubham $best$ $solution$ 0 votes 0 votes Harshit Dubey commented Jul 30, 2023 reply Follow Share @Sachin Mittal 1 sir to which topic of Algorithm can I relate this question to ? 1 votes 1 votes Please log in or register to add a comment.
3 votes 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 ??? Digvijay Pandey answered Mar 12, 2015 Digvijay Pandey comment Share Follow See 1 comment See all 1 1 comment reply rajinder singh commented Sep 9, 2018 reply Follow Share I think ,In question movements are allowed not the jumps .So we cannot put 31 directly in place of 1. 0 votes 0 votes Please log in or register to add a comment.
2 votes 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. Vikrant Singh answered Feb 12, 2015 edited Feb 20, 2015 by Vikrant Singh Vikrant Singh comment Share Follow See all 11 Comments See all 11 11 Comments reply Arjun commented Feb 18, 2015 reply Follow Share 2 left, 4 up, 6 left, 18 up, won't do? 1 votes 1 votes Pragy Agarwal commented Feb 19, 2015 i edited by Pragy Agarwal Feb 19, 2015 reply Follow Share @Arjun sir: 25 and $\infty$ too must be shifted left after shifting 18. 1 votes 1 votes Pragy Agarwal commented Feb 19, 2015 reply Follow Share @Vikrant Singh: The shifts you make will give the following matrix: 2 5 14 23 3 4 6 25 10 12 18 ∞ 31 ∞ ∞ ∞ 2 votes 2 votes Arjun commented Feb 19, 2015 reply Follow Share missed 25 :( . But the above table is fine rt? 0 votes 0 votes Pragy Agarwal commented Feb 19, 2015 reply Follow Share 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 3 votes 3 votes Arjun commented Feb 19, 2015 reply Follow Share I missed that too. But as per the question we needn't shift infinity. Once an element is shifted that entry becomes infinity. 1 votes 1 votes Pragy Agarwal commented Feb 19, 2015 reply Follow Share 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$ 2 votes 2 votes Arjun commented Feb 19, 2015 reply Follow Share "unfilled entries may be filled with an infinity" So, we have a choice here :) 2 votes 2 votes kshirsagar1992 commented Feb 20, 2015 reply Follow Share @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 votes 1 votes Anu007 commented Dec 14, 2017 reply Follow Share @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? 1 votes 1 votes Pranavpurkar commented Jul 6, 2022 reply Follow Share sir, i think here they are saying that unfilled entries at the end of shift will be marked as infinite. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Answer: 6 Shift $2,4,6,18,25, \infty$ in a zig-zag manner. 2 4 5 14 3 6 18 23 10 12 25 ∞ 31 ∞ ∞ ∞ Pragy Agarwal answered Feb 19, 2015 edited Feb 19, 2015 by Pragy Agarwal Pragy Agarwal comment Share Follow See all 3 Comments See all 3 3 Comments reply Vikrant Singh commented Feb 19, 2015 reply Follow Share I don't think we need to count ∞ shift. we just have to fill the unfilled entries. 0 votes 0 votes Digvijay Pandey commented Mar 12, 2015 reply Follow Share there cannot be any entry to the right of, or below a ∞.. entry 31 violate this condition.. der is infinity after 25.. correct me .. –1 votes –1 votes Pragy Agarwal commented Mar 13, 2015 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes 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 Akash Papnai answered Nov 4, 2019 Akash Papnai comment Share Follow See all 0 reply Please log in or register to add a comment.