Carousel Draft Recovery
Final array from integer commands that append, undo, or redo
A social network lets a creator build a draft carousel by adding post cards. The editor records a sequence of integer commands in commands:
- A positive integer adds a card with that post ID to the end of the draft.
0means undo: remove the last card in the draft and make it available for recovery. If the draft is empty, do nothing.-1means redo: restore the most recently undone card to the end of the draft. If no card is available for recovery, do nothing.
Adding a new card permanently discards all cards currently available for recovery, even if the new card has the same ID as a discarded card. Undo and redo commands that do nothing do not discard recoverable cards.
The draft starts empty. The same post ID may appear more than once, and each occurrence is a separate card.
Return the post IDs in the final draft, in their displayed order from first to last.
Examples
Example 1
Input: commands = [14,27,0,-1,35] Output: [14,27,35]
The creator adds cards 14 and 27, undoes card 27, and then restores it. Adding card 35 puts it at the end of the draft.
Example 2
Input: commands = [5,8,0,0,-1,11,-1] Output: [5,11]
Two undo commands remove cards 8 and 5. Redo restores card 5 first. Adding card 11 discards the remaining recoverable card 8, so the final redo command does nothing.
Example 3
Input: commands = [0,-1,6,6,0,-1] Output: [6,6]
The initial undo and redo commands do nothing. The two cards with ID 6 are separate occurrences; undo removes only the last one, and redo restores that occurrence.
Constraints
- 0 <= commands.length <= 10000
- Each command is -1, 0, or an integer from 1 through 1000000000.
The intended solution takes O(n) total time and O(n) auxiliary space, where n is the number of commands. Clearing recovery history still takes O(n) total time across the entire sequence because each discarded occurrence must previously have been placed there.
Hints
Show hint 1Hint 1
Which end of the draft changes during every successful command?
Show hint 2Hint 2
Keep removed cards separately so that the most recently undone card is recovered first. A new positive command clears that recovery history.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you support a command that undoes up to k cards at once?
- How would you change the history representation if undo and redo also had to support inserting or deleting a card at any position?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem