Asked in: MICROSOFT
Image of the Question
All Testcases Passed ✔
Solution
import bisect
def minDeletions(arr):
stack = []
count = 0
// ... rest of solution available after purchaseExplanation
```
To solve this problem, the core idea is to find the minimum number of deletions needed to make the array "almost sorted." "Almost sorted" means the array can become perfectly sorted in ascending order after deleting at most one more element. Another way to look at this is: after removing some elements, the resulting array should require at most one more deletion to be strictly sorted.
This problem involves a blend of understanding longest increasing subsequences, careful analysis of the order of elements, and verifying how many elements disrupt the sorted order.
Here’s the step-by-step thinking process:
1. **Understanding the problem and key definitions**
The array is composed of unique integers, which simplifies some comparisons. We want to remove the minimum number of elements to reach an array where removing at most one more element results in a fully sorted ascending array.
So, after our removals, the resulting array is either already sorted or is one deletion away from being sorted.
2. **What does "almost sorted" mean in terms of array properties?**
An array is sorted if each element is less than the next. If the array is not sorted, we want it to be "almost sorted" – meaning removing one element from this array will make it sorted.
Thus, if the array has zero or one "violation" (a place where a[i] > a[i+1]), it’s almost sorted.
3. **Approach overview: reducing problem complexity**
The main difficulty is to figure out which elements to remove so that the leftover array is almost sorted. The array size can be up to 10^5, which means the solution must be efficient, ideally O(n log n) or O(n).
4. **Longest Increasing Subsequence (LIS) Insight**
The LIS of an array is the longest subsequence of elements that are sorted ascending. Removing elements outside the LIS makes the array sorted.
However, in this problem, we want an array that is almost sorted, not necessarily perfectly sorted. Therefore, just finding the LIS is not enough, but it's a good starting point.
- If the LIS length is `L`, removing `n - L` elements will result in a sorted array.
- But since we want the array to be almost sorted (allowing one more deletion to fix the array), we might need fewer removals.
5. **Check how to relax the strict sortedness condition**
After deletions, if the array is almost sorted, it means it has at most one violation (at most one pair where a[i] > a[i+1]).
So, instead of forcing the array to be perfectly sorted, we can tolerate one violation. This gives us a bit more flexibility to keep more elements, meaning fewer removals.
6. **Working with subsequences and deletions**
We want to find a subsequence (not necessarily contiguous) of the original array that is "almost sorted." The problem reduces to finding the longest subsequence where the number of violations is at most one.
The minimal deletions will be `n` minus the length of this subsequence.
7. **How to find such a subsequence?**
One way is to consider two pointers or dynamic programming approaches:
- Iterate over the array and track increasing runs and where violations occur.
- If more than one violation occurs, consider removing an element to fix that violation and continue.
- You can check segments that are nearly sorted except for one violation and try to merge them to form a longer almost sorted subsequence.
8. **Practical algorithmic outline**
- Iterate through the array and find all places where `arr[i] > arr[i+1]` (violations).
- If violations are zero or one already, no removals needed or minimal removals are zero or one.
- If more than one violation exists, investigate removing elements around these violations to reduce their count to at most one.
- To minimize deletions, prefer removing elements causing the maximum disruption (e.g., the element causing the violation or its neighbors).
- This can be done by simulating removals around violation points and checking the length of the resulting subsequence.
- The minimal removal count is the smallest number of deletions among all such attempts.
9. **Optimizations and considerations**
- Since all elements are distinct, violations are strictly defined and can be identified quickly.
- Use efficient scanning and possibly binary search to check subsequences.
- Consider edge cases: arrays already sorted (zero deletions), arrays that require one removal to be sorted (one deletion), and arrays that cannot be fixed with one removal after a certain deletion.
10. **Final solution perspective**
The final answer is the minimum number of elements that must be removed to get to an array where at most one violation exists (i.e., the array is almost sorted).
You find the longest almost sorted subsequence, then subtract its length from `n` to get the number of deletions.
**Summary:**
- Analyze violations in the array to understand how "unsorted" it is.
- Try to find the longest subsequence with at most one violation.
- Minimize removals by carefully deciding which elements to delete around violations.
- This involves scanning for violations, simulating removals, and using subsequence logic to maintain efficiency.
By focusing on the violation points and leveraging the almost sorted definition, you can find the minimal removals required efficiently without enumerating all subsets.
```