Problem 12.4 · RecursionMedium

Tower of Hanoi

What it teaches: The classic leap of faith: to move n discs, trust that you can move n − 1 discs, twice.

The problem

Move n discs from peg 1 to peg 3 using peg 2 as a helper. Only one disc moves at a time, and a larger disc never goes on a smaller one. Return the list of moves as strings like "1->3".

Example 1

Input: n = 1
Output: ["1->3"]

Example 2

Input: n = 2
Output: ["1->2", "1->3", "2->3"]

Constraints

1 ≤ n ≤ 10

Pattern clues in the wording

→ The problem for n contains the problem for n − 1
→ Exponential output size (2ⁿ − 1 moves)

These clues point to Recursion: Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<String> hanoi(int n) {
        List<String> moves = new ArrayList<>();
        return moves;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 1	["1->3"]
2	n = 2	["1->2","1->3","2->3"]
3	n = 3	["1->3","1->2","3->2","1->3","2->1","2->3","1->3"]

From slow to fast

Approaches

1. Optimal: recursive three steps · O(2ⁿ)

Optimal: recursive three steps

Time O(2ⁿ) Space O(n) stack (plus the output)

solve(n, from, to, via): if n == 0 return. solve(n − 1, from, via, to); record from->to; solve(n − 1, via, to, from).

▶ Dry run: Moving two discsn = 2

peg 1(stack)

peg 2(stack)

empty

peg 3(stack)

empty

Step 1/4Disc 2 (big) is under disc 1 (small). Step 1: move the n − 1 = 1 small disc to peg 2.

Approach 1

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> hanoi(int n) {
        List<String> moves = new ArrayList<>();
        solve(n, 1, 3, 2, moves);
        return moves;
    }

    private void solve(int n, int from, int to, int via, List<String> moves) {
        if (n == 0) return;
        solve(n - 1, from, via, to, moves);
        moves.add(from + "->" + to);
        solve(n - 1, via, to, from, moves);
    }
}

Verdict: 2ⁿ − 1 moves is the minimum possible, so no algorithm can do better.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1

Mistakes people make

Swapping the roles of 'to' and 'via' in the recursive calls.

Interview

Follow-up questions

Why exactly 2ⁿ − 1 moves?

Command Palette

The problem

Approaches

Optimal: recursive three steps

Edge cases and common mistakes

Follow-up questions