Solution: Minimum Deletions to Make a Sequence Sorted

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Minimum Deletions to Make a Sequence Sorted

Table of Contents

Contents are not accessible

Problem Statement

Given a number sequence, find the minimum number of elements that should be deleted to make the remaining sequence sorted.

Example 1:

Input: {4,2,3,6,10,1,12}
Output: 2
Explanation: We need to delete {4,1} to make the remaing sequence sorted {2,3,6,10,12}.

Example 2:

Input: {-4,10,3,7,15}
Output: 1
Explanation: We need to delete {10} to make the remaing sequence sorted {-4,3,7,15}.

Example 3:

Input: {3,2,1,0}
Output: 3
Explanation: Since the elements are in reverse order, we have to delete all except one to get a 
sorted sequence. Sorted sequences are {3}, {2}, {1}, and {0}

Basic Solution

A basic brute-force solution could be to try deleting all combinations of elements, one by one, and checking if that makes the subsequence sorted.

Alternately, we can convert this problem into a "Longest Increasing Subsequence" (LIS) problem. As we know that LIS will give us the length of the longest increasing subsequence (in the sorted order!), which means that the elements which are not part of the LIS should be removed to make the sequence sorted. This is exactly what we need. So we'll get our solution by subtracting the length of LIS from the length of the input array: Length-of-input-array - LIS()

Let's jump directly to the bottom-up dynamic programming solution.

Bottom-up Dynamic Programming

Here is the code for our bottom-up dynamic programming approach:

Python3

. . . .

The time complexity of the above algorithm is $O(n^2)$ and the space complexity is $O(n)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible