Determine whether an array can be made non-decreasing by repeatedly removing adjacent pairs under the problem's allowed operation.
You are given an integer array nums. You may repeatedly choose a valid adjacent pair and remove it from the array. Your task is to determine the minimum number of pair-removal operations needed so that the remaining array is sorted in non-decreasing order. If the array is already sorted, the answer is 0.
In this version of the problem, the key challenge is to reason about how pair removals affect the relative order of the remaining elements and to compute the smallest number of operations needed rather than trying all possibilities explicitly.
Input Format
Input
- An integer array
nums.
Interpretation
- Each operation removes one adjacent pair from the current array.
- After any number of operations, the remaining elements must be in non-decreasing order.
Output Format
Output
- Return the minimum number of pair-removal operations required to make the remaining array non-decreasing.
- If it is impossible, return
-1.
Constraints
1 <= nums.lengthis assumed to be manageable for interview-style reasoning.- Array values may be negative, zero, or positive.
- The operation removes exactly two adjacent elements each time.
Example 1
Input
nums = [3, 1, 2, 4]
Output
1
Explanation
Remove the adjacent pair [3, 1]. The remaining array is [2, 4], which is non-decreasing.
Example 2
Input
nums = [1, 2, 3, 4]
Output
0
Explanation
The array is already non-decreasing, so no removals are needed.
Show 1 more example
Example 3
Input
nums = [4, 3, 2, 1]
Output
2
Explanation
Remove [4, 3] and then remove [2, 1]. Nothing remains, which is trivially non-decreasing.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.