Fewest Removals to Sorted

Medium1-D Dynamic Programming

Problem

A conveyor belt carries parcels with sizes sizes, in this order. You may lift parcels off the belt, but you cannot reorder the ones that stay.

Return the minimum number of parcels to remove so that the remaining sizes are non-decreasing from front to back. The belt can be long, so an O(n²) approach is too slow.

Example 1

Input:
sizes = [4, 1, 3, 2, 5]
Output:
2

Keep 1, 3, 5 (or 1, 2, 5): three parcels stay, two are removed.

Example 2

Input:
sizes = [1, 2, 2, 3]
Output:
0

Already non-decreasing; equal sizes may stay side by side.

Constraints

  • 1 ≤ sizes.length ≤ 10^5
  • 1 ≤ sizes[i] ≤ 10^9
  • Target O(n log n).

Hint

Show the first hint

Removing the fewest parcels is the same as keeping the most: the longest non-decreasing subsequence.

Walkthrough

How to approach it

01Clarify before coding

  • Non-decreasing or strictly increasing? Non-decreasing: equal neighbours are fine.
  • Can I reorder? No, only remove.
  • How large is n? Up to 10^5, so the O(n²) subsequence DP (5·10^9 steps) is out.

02Brute force

Classic DP: keep[i] = 1 + max(keep[j]) over j < i with sizes[j] ≤ sizes[i]; answer n - max(keep).

Cost: O(n²) time: correct, but about 5·10^9 comparisons for 10^5 parcels.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.