Company: wayfair_26oct
Difficulty: medium
Almost Sorted Problem Description An array of integers is almost sorted if at most one element can be deleted to make it perfectly sorted in ascending order. Your task is to determine the minimum number of elements to remove so the array becomes almost sorted. Example: Consider arr = [3, 4, 2, 5, 1] If we remove 2, we get arr' = [3, 4, 5, 1] If we remove 1, we get arr' = [3, 4, 2, 5] Both resulting arrays are almost sorted since we can remove one more element to make them perfectly sorted. The minimum number of elements that must be removed is 1. Function Description Complete the function minDeletions in the editor with the following parameter(s): int arr[n] : an unsorted array of integers Returns int : the minimum number of items that must be deleted to create an almost sorted array Examples Example 1: Input: 5 1 2 6 4 3 Output: 1 Explanation: One can remove for example 4 to get [1, 2, 6, 3] which is almost sorted. Other choices are to remove 6 or 3. The minimum number of elements tha