Problem 375678 · hard · Phase 03 Linear Management & Searching

Pulling Forms to the Top of the Tray

sorting · greedy · minimum moves · duplicates

A tray holds forms with priority numbers forms; forms[0] is on top. One move pulls any single form out of the tray and places it on top. Return the minimum number of moves needed so that the priorities read in non-decreasing order from top to bottom.

Examples

Input:  forms = [3, 1, 2]
Output: 2
Explanation: pull 2 to the top ([2, 3, 1]), then pull 1 ([1, 2, 3]).
Input:  forms = [2, 1, 2, 3, 1]
Output: 2
Explanation: pull the last 1 ([1, 2, 1, 2, 3]), then the other 1 ([1, 1, 2, 2, 3]).

Constraints

  • 0 <= len(forms) <= 10**5
  • 0 <= forms[i] <= 10**9
  • An O(n log n) solution is expected.

Goals

  • Reason about which items are never moved instead of simulating moves
  • See that the untouched items must be the largest values, in order
  • Handle repeated values, where only some copies can stay put
Starting Python…