GATE CS 2024 Set 2 Q25 — Searching, Sorting, Hashing

To find the minimum number of elements that must be replaced to make the array sorted in non-decreasing order, we should keep as many elements in their original relative order as possible. These kept elements must form a Longest Non-Decreasing Subsequence (LNDS) of the array.

If $n$ is the length of the array and $L$ is the length of its LNDS, then the minimum number of replacements (distance) is given by:

For the given array $A = [2, 5, 3, 1, 4, 2, 6]$ of size $n = 7$:

• Let's find the LNDS of $A$.
• One such longest non-decreasing subsequence is $[2, 3, 4, 6]$ (corresponding to indices $0, 2, 4, 6$).
• The length of this subsequence is $L = 4$.

Thus, the minimum number of elements to replace is:

For example, by replacing the elements at indices $1, 3,$ and $5$ (which are $5, 1,$ and $2$), we can obtain the sorted array $[2, 2, 3, 3, 4, 5, 6]$ with exactly $3$ replacements.