# Minimum Deletions to Make a Sequence Sorted

Let's solve the Minimum Deletions to Make a Sequence Sorted problem using Dynamic Programming.

We'll cover the following

## 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 6000$
• $-10^9 \leq$ nums[i] $\leq 10^9$

## Examples

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.