AlgoInsight

DSA problem

Tower of Hanoi

MediumRecursionPattern: RecursionbeginnerFree

Given N disks stacked in decreasing size on a source rod, move all disks to a destination rod using an auxiliary rod. Rules: only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller disk. Return the ordered list of moves.

The solution is beautifully simple once seen. To move N disks from source to destination using auxiliary:

  1. Move the top N-1 disks from source to auxiliary (using destination as the temporary rod).
  2. Move disk N directly from source to destination.
  3. Move the N-1 disks from auxiliary to destination (using source as the temporary rod).

Two of the three steps are recursive calls on a smaller problem. The number of moves required is 2^N - 1, which grows exponentially - for the legendary 64 disks that is over 18 quintillion moves. This problem is a masterclass in trust the recursion: understand the one-level decomposition and trust the recursive calls to handle the rest.

Examples

Example 1
Input: N = 3, source = "A", auxiliary = "B", destination = "C"
Output: ["Move disk 1 from A to C", "Move disk 2 from A to B", "Move disk 1 from C to B", "Move disk 3 from A to C", "Move disk 1 from B to A", "Move disk 2 from B to C", "Move disk 1 from A to C"]
Explanation: 7 = 2^3 - 1 moves. The top 2 disks are relocated to B, disk 3 moves from A to C, then the 2 disks move from B to C.
Example 2
Input: N = 1, source = "A", auxiliary = "B", destination = "C"
Output: ["Move disk 1 from A to C"]
Explanation: The base case: a single disk moves straight from source to destination.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

recursiondivide-and-conquer

Browse all DSA problems