Title: Minimum Number of Deletions to Make an Array Sorted
Sorting problems often hide a subtler question: what is the smallest edit that gets you there? In this guide, you’ll learn how to find the minimum number of elements you must delete from an integer array so that what remains is sorted in non-decreasing order.
We’ll build the solution around a classic interview idea, the longest non-decreasing subsequence, walk through a full Java program, trace it on a sample array, and cover the edge cases and follow-up questions an interviewer is likely to ask.
Understanding the Problem
Given an integer array nums, you need to remove the fewest elements possible so that the elements left behind, in their original order, form a non-decreasing sequence. Deleted elements are discarded; the remaining elements keep their relative order.
Since every element you keep must still read left to right as non-decreasing, maximizing what you keep is the same problem as finding the longest non-decreasing subsequence, or LNDS, hidden inside nums. Once you know that length, the deletions are simply the elements that did not make the cut.
For example, in nums = {5, 3, 4, 9, 6, 1, 7}, the subsequence {3, 4, 6, 7} is non-decreasing and has length 4, the longest one available. The other 3 elements, 5, 9, and 1, must be deleted.
Approach
- Read the array
numsof lengthn. Ifnis 0 or 1, the array is already sorted, so the answer is 0. - Create a
dparray of sizenwheredp[i]stores the length of the longest non-decreasing subsequence that ends exactly at indexi. - Initialize every
dp[i]to 1, since each element alone is always a valid subsequence of length 1. - For each index
ifrom 0 ton - 1, check every earlier indexjfrom 0 toi - 1. Ifnums[j] <= nums[i], the element atican extend the subsequence ending atj, so setdp[i] = Math.max(dp[i], dp[j] + 1). - Track the largest value seen across the whole
dparray as you go; call itlongest. - Return
n - longestas the minimum number of deletions, since every element outside that longest subsequence has to be removed.
Java Program
public class MinimumDeletionsToSort {
public static int minimumDeletions(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] dp = new int[n];
int longest = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
longest = Math.max(longest, dp[i]);
}
return n - longest;
}
public static void main(String[] args) {
int[] nums = {5, 3, 4, 9, 6, 1, 7};
int deletions = minimumDeletions(nums);
System.out.println("Minimum deletions required: " + deletions);
}
}Explanation of the Program
The method minimumDeletions implements the dynamic programming approach described above.
dp[i]is seeded to 1 for every index before the comparisons run, matching the base case that a single element is always non-decreasing on its own.- The nested loop compares
nums[i]against every earliernums[j]. The conditionnums[j] <= nums[i]allows duplicates, since a sequence like{2, 2, 2}is still non-decreasing. longestis updated after each outer iteration so it always reflects the best subsequence length found so far, including one that might end at the very last index.- The final line subtracts
longestfromn, because the elements outside the longest non-decreasing subsequence are exactly the ones that need deleting.
Step-by-Step Trace
Let's trace the algorithm on nums = {2, 5, 3, 4, 1, 6}, a 6-element array chosen to show both a successful extension and an index where no earlier element qualifies.
| i | nums[i] | dp[i] before | Extends an earlier index? | dp[i] after |
|---|---|---|---|---|
| 0 | 2 | 1 | no (first element) | 1 |
| 1 | 5 | 1 | yes, extends index 0 (2 <= 5) | 2 |
| 2 | 3 | 1 | yes, extends index 0 (2 <= 3) | 2 |
| 3 | 4 | 1 | yes, extends index 2 (3 <= 4) | 3 |
| 4 | 1 | 1 | no (no earlier value <= 1) | 1 |
| 5 | 6 | 1 | yes, extends index 3 (4 <= 6) | 4 |
At the end of iteration i, dp[i] holds the length of the longest non-decreasing subsequence that ends exactly at index i, so the maximum value across dp after the loop finishes is the longest non-decreasing subsequence in the whole array. Here that maximum is 4, so the answer is 6 - 4 = 2 deletions.
Examples
Example 1: An Already Sorted Array With Duplicates
nums = {1, 2, 2, 3, 5} is already non-decreasing, and the repeated 2 does not count against it, since the comparison allows equal neighbors.
int[] nums = {1, 2, 2, 3, 5};
System.out.println("Minimum deletions required: " + minimumDeletions(nums));
// Output: Minimum deletions required: 0Example 2: A Strictly Decreasing Array
nums = {9, 7, 5, 3, 1} has no two elements in non-decreasing order, so the longest non-decreasing subsequence is any single element.
int[] nums = {9, 7, 5, 3, 1};
System.out.println("Minimum deletions required: " + minimumDeletions(nums));
// Output: Minimum deletions required: 4Common Mistakes to Avoid
A few habits trip up candidates solving this exact problem. Watch for these before they turn into bugs.
- Treating equal elements as out of order - using
nums[j] < nums[i]instead ofnums[j] <= nums[i]wrongly forces a deletion whenever two equal values sit next to each other. Use<=so duplicates stay allowed. - Counting adjacent descents instead of the subsequence - scanning once for places where
nums[i] > nums[i + 1]and counting those spots undercounts or overcounts whenever one deletion fixes several inversions at once. Compute the longest non-decreasing subsequence instead of counting local drops. - Returning the subsequence length instead of the deletions - reporting
longestdirectly answers 'how many elements can I keep', not 'how many must I delete'. Always returnn - longest. - Updating
longestonly inside the inner loop - if theMath.max(longest, dp[i])call sits inside thejloop instead of after it, the best subsequence ending at the final index can be missed. Updatelongestonce per outer iteration, after the inner loop completes.
Edge Cases to Test
Before calling the solution done, run it against these input shapes.
- Empty array
- Single-element array
- Already non-decreasing array
- Strictly decreasing array
- All identical elements
- Duplicate values scattered non-adjacently
- Array containing negative numbers
- Large array (performance of the O(n^2) approach)
Additional Considerations
The dynamic programming solution runs in O(n^2) time, since for every index i it scans all earlier indices j. It uses O(n) extra space for the dp array on top of the input.
The O(n^2) time comes directly from the nested loop and is usually fine for interview-sized inputs, but it becomes a bottleneck once n reaches tens of thousands of elements.
The same problem can be solved in O(n log n) time with the patience-sorting technique used for the Longest Increasing Subsequence: maintain a tails array of the smallest possible tail value for each subsequence length, and binary search it for each new element. Using an upper-bound search instead of a lower-bound search adapts that technique from strictly increasing to non-decreasing. The O(n^2) version is worth knowing first because it maps directly onto the problem statement and is easier to explain and debug.
Interview Follow-up Questions
Once you've solved the base problem, an interviewer will usually push on these variants.
- What if the remaining array must be strictly increasing instead of non-decreasing? - change the comparison to
nums[j] < nums[i]so that equal neighbors now count as an inversion requiring a deletion. - What if
ncan be up to 100000 or more? - theO(n^2)DP is too slow; replace it with theO(n log n)tails-array approach built on binary search. - What if you need the actual elements to delete, not just the count? - keep a parent pointer alongside
dp[i]recording which earlier index it extended, then walk backward from the index with the largestdpvalue to mark which indices are kept, and delete the rest. - What if the array arrives as a stream and you cannot look ahead? - maintain the tails array incrementally with a binary search insertion per incoming element; you can always report the best answer seen so far, you just cannot revise earlier decisions once new elements make a longer subsequence possible.
Conclusion
The minimum number of deletions to make an array sorted comes down to one reframing: keep the longest non-decreasing subsequence you can find, and delete everything else. The dynamic programming solution shown here is the natural first approach, and it generalizes cleanly to the strictly increasing variant and to larger inputs once you reach for the binary search optimization.
Try adapting the program to return the kept indices instead of just the count, and compare your trace against the one above on a few arrays of your own. You can learn more about array-based algorithms like this one on our Arrays category page.



