Advertisement
Home Data Structure Arrays Minimum Number of Deletions to Make an Array Sorted

Minimum Number of Deletions to Make an Array Sorted

0
Advertisement

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

  1. Read the array nums of length n. If n is 0 or 1, the array is already sorted, so the answer is 0.
  2. Create a dp array of size n where dp[i] stores the length of the longest non-decreasing subsequence that ends exactly at index i.
  3. Initialize every dp[i] to 1, since each element alone is always a valid subsequence of length 1.
  4. For each index i from 0 to n - 1, check every earlier index j from 0 to i - 1. If nums[j] <= nums[i], the element at i can extend the subsequence ending at j, so set dp[i] = Math.max(dp[i], dp[j] + 1).
  5. Track the largest value seen across the whole dp array as you go; call it longest.
  6. Return n - longest as the minimum number of deletions, since every element outside that longest subsequence has to be removed.

Java Program

Java
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 earlier nums[j]. The condition nums[j] <= nums[i] allows duplicates, since a sequence like {2, 2, 2} is still non-decreasing.
  • longest is 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 longest from n, 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.

inums[i]dp[i] beforeExtends an earlier index?dp[i] after
021no (first element)1
151yes, extends index 0 (2 <= 5)2
231yes, extends index 0 (2 <= 3)2
341yes, extends index 2 (3 <= 4)3
411no (no earlier value <= 1)1
561yes, 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.

Java
int[] nums = {1, 2, 2, 3, 5};
System.out.println("Minimum deletions required: " + minimumDeletions(nums));
// Output: Minimum deletions required: 0

Example 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.

Java
int[] nums = {9, 7, 5, 3, 1};
System.out.println("Minimum deletions required: " + minimumDeletions(nums));
// Output: Minimum deletions required: 4

Common 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 of nums[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 longest directly answers 'how many elements can I keep', not 'how many must I delete'. Always return n - longest.
  • Updating longest only inside the inner loop - if the Math.max(longest, dp[i]) call sits inside the j loop instead of after it, the best subsequence ending at the final index can be missed. Update longest once 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 n can be up to 100000 or more? - the O(n^2) DP is too slow; replace it with the O(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 largest dp value 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.