GATE 2024 CS (CS2) – Question 35
Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2,5,3,1,4,2,6]$ is ___________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
Distance = n − length of the longest non-decreasing subsequence. LNDS is 4 (e.g., 2,3,4,6), so distance = 7 − 4 = 3.