GATE CS 2015 Set 2 Q31 — Arrays, Stacks and Queues

To remove the minimum element (which is $1$ at cell $(0,0)$) from a Young tableau while preserving its properties, we perform a procedure similar to heapify-down:

1. Replace the element to be deleted with $\infty$.
2. Compare the current cell with its right neighbor and its bottom neighbor.
3. Swap (or shift) the smaller of the two neighbors into the current cell.
4. Repeat this process for the empty cell until both neighbors are $\infty$ or out of bounds.

Let's trace the step-by-step shifts starting from $(0,0)$ after removing $1$:

• Step 1: At $(0,0)$, neighbors are $2$ (right) and $3$ (bottom). Since $2 < 3$, we shift $2$ to $(0,0)$. The empty cell is now at $(0,1)$.
• Step 2: At $(0,1)$, neighbors are $5$ (right) and $4$ (bottom). Since $4 < 5$, we shift $4$ to $(0,1)$. The empty cell is now at $(1,1)$.
• Step 3: At $(1,1)$, neighbors are $6$ (right) and $12$ (bottom). Since $6 < 12$, we shift $6$ to $(1,1)$. The empty cell is now at $(1,2)$.
• Step 4: At $(1,2)$, neighbors are $23$ (right) and $18$ (bottom). Since $18 < 23$, we shift $18$ to $(1,2)$. The empty cell is now at $(2,2)$.
• Step 5: At $(2,2)$, neighbors are $25$ (right) and $\infty$ (bottom). Since $25 < \infty$, we shift $25$ to $(2,2)$. The empty cell is now at $(2,3)$.
• At $(2,3)$, both neighbors are $\infty$ (or out of bounds), so the process terminates by placing $\infty$ at $(2,3)$.

The elements shifted are $2, 4, 6, 18,$ and $25$. Thus, the minimum number of entries shifted is $5$.