Implementing Undo: 3 Approaches and Tradeoffs
Three universally applicable approaches to undo: Direct Reversal, Replay from Scratch, and Snapshot History. Tradeoffs for time and space.
In a machine coding interview, "Undo" is often the feature that tests if your design is flexible. If you have hardcoded your state changes, undo becomes a nightmare. If you have a clean history of moves, it becomes a logic exercise. Here are the three ways to approach it.
The Essentials
- Approach 1: Direct Reversal. Perform the exact inverse of a move (e.g., set cell to empty). Fast (O(1)) but requires every action to be reversible.
- Approach 2: Replay from Scratch. Clear the state and re-apply all moves except the last one. Reliable but slow (O(N)) as history grows.
- Approach 3: Snapshot History. Save the entire state (Board) after every move. Simple and O(1), but consumes significant memory (O(N) space).
- TicTacToe uses Direct Reversal. The actions are simple (cell filling, player rotation) and easy to invert.
Approach 1: State Reversal (The Mirror)
ExpandState Reversal Diagram
This is the most memory-efficient approach.
You store a list of Move objects. When undo is called, you take the last move and perform its inverse.
- Move: Set cell to
FILLEDwith symbolX. - Inverse Move: Set cell back to
EMPTY.
In TicTacToe, this involves clearing the cell and rotating the currentPlayerIndex backward.
// Direct Reversal
undo(): void {
if (this.moves.length === 0) return;
const lastMove = this.moves.pop()!;
lastMove.getCell().clear(); // Set to EMPTY
// Reverse turn index
this.currentPlayerIndex = (this.currentPlayerIndex - 1 + this.players.length) % this.players.length;
// Notify strategies to decrement their counts
this.winningStrategies.forEach(s => s.handleUndo(this.board, lastMove));
this.gameStatus = GameStatus.IN_PROGRESS;
}Tradeoffs:
- Pros: Extremely fast (O(1)) and uses minimal extra memory.
- Cons: You must manually write the inverse logic for every single action. If your game has complex, cascading state changes (like in Chess or Ludo), direct reversal can become very complex and error-prone.
Approach 2: Replay from Scratch
If direct reversal is too complex, you can clear the entire board and re-apply the first N-1 moves from history.
Tradeoffs:
- Pros: Zero risk of state corruption. You use the exact same
makeMovelogic you already wrote. No inverse logic needed. - Cons: Time complexity is O(N) where N is the number of moves. For a 3x3 board, this is fine. for a massive game with thousands of moves, the performance hit is noticeable.
Approach 3: Snapshot History (Memento Pattern)
Every time a move is made, you create a deep copy (a snapshot) of the entire board and store it in a stack. To undo, you simply pop the stack and set the current board to the previous snapshot.
Tradeoffs:
- Pros: O(1) time complexity and extremely simple to implement.
- Cons: O(N * S) space complexity where S is the size of the board. Storing 100 snapshots of a 100x100 grid can quickly consume megabytes of memory.
Which One to Choose?
In an interview, I always start by suggesting Direct Reversal if the operations are simple. It shows that I can reason about state transitions.
If the game involves complex rules (like capturing pieces in Chess), I might suggest Replay from Scratch as a more robust alternative. I then discuss the performance tradeoff to show I am aware of the O(N) cost.
For TicTacToe, we will use Direct Reversal because the operations are perfectly invertible. We will see this implemented in the final coding session. But first, we need to solve the O(1) winner detection problem.
Further Reading and Watching
Practice what you just read.
Keep reading