Minimum Deletions to Make Sorted

Problem Overview

To make the array sorted with the fewest deletions, keep the longest subsequence that is already non-decreasing and delete the rest.

Intuition

To make the array sorted with the fewest deletions, keep the longest subsequence that is already non-decreasing and delete the rest. Minimum deletions = n − LIS length. Patience sorting builds that LIS length in O(n log n) by maintaining the smallest possible tail for every subsequence length.

Algorithm

1Maintain a list lis of tails: lis[len−1] is the smallest ending value of any non-decreasing subsequence of length len.
2For each num, binary-search the first position where lis[pos] ≥ num (strictly, first ≥ for non-decreasing).
3If pos is inside the list, replace lis[pos] = num; otherwise append num (new longest length).
4Return arr.length − lis.size().

Example Walkthrough

Input: arr = [5, 3, 4, 2, 6]

1. 5 → lis = [5].
2. 3 → replace → [3].
3. 4 → append → [3, 4].
4. 2 → replace first → [2, 4]; 6 → append → [2, 4, 6].
5. LIS length = 3 (e.g. 3,4,6); deletions = 5 − 3 = 2.

Output: 2

Common Pitfalls

• Use lower_bound (≥), not upper_bound (>), when equals are allowed in a non-decreasing sort.
• The tails array is not itself an LIS — only its length equals the LIS length.
• Empty array → 0 deletions.
• Already sorted → LIS = n → answer 0; strictly decreasing → LIS = 1 → answer n − 1.

Minimum Deletions to Make Sorted.java

Java


import java.util.*;

class Solution {

    // Approach: The longest non-decreasing subsequence can stay; everything else
    // must be deleted. Compute LIS length with patience sorting (tails array +
    // binary search for the first tail >= num), then answer = n − LIS length.
    // Complexity: O(n log n) time and O(n) space.
    public int minDeletions(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        ArrayList<Integer> lis = new ArrayList<>();
        for (int num : arr) {
            // Find the position of the first element >= num
            int pos = binarySearch(lis, num);
            // If the element is not found, binarySearch returns -(insertion_point) - 1
            if (pos < 0) {
                pos = -(pos + 1);
            }
            // If pos is within bounds, replace the element to maintain the smallest possible tail
            if (pos < lis.size()) {
                lis.set(pos, num);
            } else {
                lis.add(num);
            }
        }
        // Minimum deletions = Total length - LIS length
        return arr.length - lis.size();
    }

    private int binarySearch(ArrayList<Integer> list, int num) {
        int l = 0, h = list.size();
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (list.get(mid) < num) {
                l = mid + 1;
            } else {
                h = mid;
            }
        }
        return l;
    }
}

Was this solution helpful?