Solution Minimum Deletions to Make a Sequence Sorted
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:
class Solution {
public int findMinimumDeletions(int[] nums) {
// subtracting the length of LIS from the length of the input array to get minimum number of deletions
return nums.length - findLISLength(nums);
}
private int findLISLength(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) if (nums[i] > nums[j] && dp[i] <= dp[j]) {
dp[i] = dp[j] + 1;
maxLength = Math.max(maxLength, dp[i]);
}
}
return maxLength;
}
public static void main(String[] args) {
Solution mdss = new Solution();
int[] nums = { 4, 2, 3, 6, 10, 1, 12 };
System.out.println(mdss.findMinimumDeletions(nums));
nums = new int[] { -4, 10, 3, 7, 15 };
System.out.println(mdss.findMinimumDeletions(nums));
nums = new int[] { 3, 2, 1, 0 };
System.out.println(mdss.findMinimumDeletions(nums));
}
}
The time complexity of the above algorithm is
🤖 Don't fully get this? Learn it with Claude
Stuck on Solution Minimum Deletions to Make a Sequence Sorted? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Progressively stronger hints — you still solve it.
I'm working on the problem **Solution Minimum Deletions to Make a Sequence Sorted** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
See the technique, not just code.
Explain the optimal approach to **Solution Minimum Deletions to Make a Sequence Sorted** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Catch bugs, edge cases, sub-optimality.
I'll paste my solution to **Solution Minimum Deletions to Make a Sequence Sorted**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Lock in recognition with look-alikes.
Give me 2 problems that use the SAME underlying pattern as **Solution Minimum Deletions to Make a Sequence Sorted**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.