Minimum Deletions to Make a Sequence Sorted

Statement

Given an integer array nums, the task is to remove or delete the minimum number of elements from the array so that the remaining elements form a strictly increasing sequence. This is very similar to the Longest Increasing Subsequence (LIS) problem because elements other than the longest increasing subsequence should be removed to make the sequence sorted.

Let’s say we have an integer array, [4, 2, 3, 6, 10, 1, 12], and we want to delete the minimum number of elements to make the remaining sequence sorted. We can do this by finding the length of the longest increasing subsequence first, which is 5 here because the longest increasing subsequence is [2, 3, 6, 10, 12]. All elements other than this should be removed to get a sorted sequence. We need to remove 4 and 1 from the array. So, the minimum number of deletions required is 2. We can formulate this relationship as:

$$Minimum \space Deletions = Array \space Length - LIS \space Length$$

Constraints:

• $1 \leq$ nums.length $\leq 5500$
• $-10^5 \leq$ nums[i] $\leq 10^5$

Examples