Determine minimal substitutions and removals

Question

Given a list of words, determine the minimum number of character substitutions required so that, in every word, no two adjacent characters are identical.

Given an array of n unique integers, determine the minimum number of elements that must be removed so the array becomes "almost sorted"—meaning that after the removals, deleting at most one additional element would make the remaining array strictly ascending.

Minimum Removals for Almost Sorted Array

Given an array of n unique integers, return the minimum number of elements to remove so that the remaining array is almost sorted. An array is almost sorted if deleting at most one additional element from it would make it strictly increasing. Removals must preserve the original relative order (i.e., the remaining elements form a subsequence of the original).

Constraints

• 0 <= n <= 200000
• All nums[i] are pairwise distinct
• -10^9 <= nums[i] <= 10^9
• Aim for O(n log n) time and O(n) extra space

Examples

Example 1

Input: nums = [3,1,2,4]
Output: 0

Explanation: The array is already almost sorted: removing the single element 3 yields [1,2,4], which is strictly increasing. Minimum initial removals is 0.

Example 2

Input: nums = [5,4,3,2,1]
Output: 3

Explanation: LIS length is 1, so we can keep at most LIS+1 = 2 elements in an almost-sorted subsequence. Thus we must remove 5 - 2 = 3 elements.

Hints

1. Let L be the length of the longest strictly increasing subsequence (LIS).
2. Any almost-sorted subsequence can become strictly increasing by removing one element, so its strictly increasing remainder cannot exceed length L.
3. You can achieve length L+1 by taking any LIS and adding one extra element; compute L with patience sorting (binary search) in O(n log n).

Approach

Let L be the LIS length of the original array. If a subsequence can be made strictly increasing by removing at most one element, then after that removal it is a strictly increasing subsequence of the original and thus has length at most L. Therefore the longest almost-sorted subsequence has length at most L+1. Conversely, you can take any LIS (length L) and add one extra element from the array (maintaining order) to obtain an almost-sorted subsequence of length L+1, since removing that extra element restores the LIS. Hence the minimum removals is n - min(n, L+1). We compute L using the patience sorting technique with binary search in O(n log n).

• Time complexity: O(n log n)
• Space complexity: O(n)