Minimum Deletions to Make a Sequence Sorted

The minimum number of deletions needed to make an array sorted equals n − LIS(arr): whatever isn't part of the longest increasing subsequence (LIS) must be removed, because the LIS is exactly the largest set of elements that can stay in place, in order, without violating sortedness.

Recognize the pattern

• Phrasing: "minimum deletions/removals to make an array sorted / strictly increasing / non-decreasing."
• You are keeping a subsequence (not contiguous, order preserved) and discarding the rest.
• The kept elements must already appear in increasing order relative to each other in the original array — that is the definitional tell for LIS.

Brute force → optimal

Brute force: enumerate every subsequence (2ⁿ of them), check if it's sorted, track the longest. Cost: O(2ⁿ · n) time, O(n) space per check — exponential, unusable beyond n≈20.

Optimal: reduce the problem to Longest Increasing Subsequence. Answer = n − LIS_length. Two standard ways to compute LIS:

1. O(n²) DP — for each index i, dp[i] = length of the longest increasing subsequence ending at i.
2. O(n log n) patience sorting — maintain a `tails` array of the smallest possible tail value for each achievable subsequence length; binary-search each new element's slot.

Complexity, derived

O(n²) DP: for each of n indices i, scan all j < i (up to n comparisons) to find the best predecessor: dp[i] = 1 + max(dp[j] for j<i, arr[j]<arr[i]). Total comparisons = 1+2+…+(n−1) = n(n−1)/2 → O(n²) time, O(n) space for the dp array.

O(n log n) patience sorting: each of n elements does one binary search over a `tails` array of length ≤ n → n · O(log n) = O(n log n) time, O(n) space for `tails`.

Traced worked example

Array: [4, 2, 3, 6, 10, 1, 12], n = 7. dp[i] = length of LIS ending at index i.

max(dp) = 5 → deletions = 7 − 5 = 2 (delete 4 and 1), matching the expected output.

Code (O(n log n))

int minDeletionsToSort(int[] arr) {
    int n = arr.length;
    int[] tails = new int[n];
    int len = 0;
    for (int x : arr) {
        int lo = 0, hi = len;
        while (lo < hi) {              // first index with tails[mid] >= x
            int mid = (lo + hi) / 2;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;
        if (lo == len) len++;
    }
    return n - len;                    // deletions = n - LIS length
}

Use strict < comparisons (as above) for a strictly increasing target; switch to <= in the search condition if the target is non-decreasing (duplicates allowed to stay).

Pitfalls

• Confusing strictly-increasing vs. non-decreasing LIS — the recurrence and binary-search comparator differ, and duplicate-heavy inputs will give wrong deletion counts if you pick the wrong one.
• `tails` holds candidate tail values, not the actual LIS — reconstructing the real kept/deleted elements needs a parent-pointer array, not just the tails array.
• Off-by-one in the binary search (using `<=` instead of `<` in the loop condition) silently breaks the O(n log n) invariant.

When to use / when not

Read the problem carefully first: this reduction applies only when elements must keep their original relative order. If the problem instead lets you freely reorder, sorting fixes everything and the deletion count is 0 — a classic misread. Use LIS reduction whenever the ask is "minimum deletions to make sorted/increasing" with order preserved — it's optimal and standard. For n ≤ ~2000, the O(n²) DP is simpler to write correctly under interview pressure and has no bugs from binary-search edge cases; prefer O(n log n) patience sorting when n is large (10⁴–10⁶) or when the interviewer explicitly asks for the tightest bound. An alternative framing — longest common subsequence of the array with its sorted copy — also finds the keep-set, but costs O(n²) time and space with no advantage over direct LIS DP, so it's mainly useful pedagogically to show LIS is a special case of LCS.

Takeaways

• Min deletions to sort = n − LIS length; the kept elements are exactly the LIS.
• O(n²) DP scans predecessors; O(n log n) patience sorting binary-searches a tails array — both derive directly from counting comparisons per element.
• Strictly-increasing vs. non-decreasing changes the comparator everywhere — decide this before coding.

Recall: Why does the length of the `tails` array at the end equal the LIS length, even though `tails` itself is not a valid subsequence of the input?

Pattern: Longest Increasing Subsequence (patience sorting / O(n²) DP), a classic interleave of DP and binary search covered in CLRS-adjacent interview references and standard LIS treatments (e.g., GeeksforGeeks, competitive programming texts).