Cracking The Coding Interview Together – Problem 8.6: Towers of Hanoi

Have you ever stared at a recursive algorithm and felt like you were peering into an endless mirror? Recursion is one of those concepts that feels like pure magic until it suddenly clicks into place as pure logic. Today, we are going to demystify one of the classic computer science puzzles that haunts technical interviews and algorithm textbooks alike: the Towers of Hanoi. When you first encounter it, the problem looks deceptively simple—move a stack of disks from point A to point C. But as we scale $N$, the underlying mechanics demand a rigorous understanding of inductive thinking and state management. By the end of this article, we will build a robust, production-ready Java solution using explicit Stacks, ensuring you can tackle both the recursive nature of the problem and the strict constraints of the prompt with absolute confidence.

Problem Statement

In the classic problem of the Towers of Hanoi, we have 3 towers and $N$ disks of different sizes which can slide onto any tower. The puzzle starts with all disks sorted in descending order of size on the first tower, meaning the smallest disk is at the top and the largest is at the bottom. Our operational goals are clear: write a program to move the entire stack of disks from the first tower to the last tower using stacks, adhering strictly to these three foundational rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
• No disk may be placed on top of a smaller disk.

Analyze the Problem Together

Let's break down the constraints and find our "Aha!" conflict. If we try to solve this iteratively for an arbitrary $N$, the state transitions quickly become a nightmare of conditional logic. However, if we think inductively, the path forward illuminates itself. Suppose we know how to move $N-1$ disks from tower A to tower B using tower C as an intermediate step. If we can do that, moving $N$ disks is trivial: we move the top $N-1$ disks to the buffer tower, move the single remaining largest disk from the source to the destination, and finally move the $N-1$ disks from the buffer tower to the destination.

The naive approach here often involves trying to simulate the physical movement of individual disks blindly based on loop indices. That approach breaks down immediately because it fails to maintain the stack invariant: LIFO (Last In, First Out). By enforcing that our towers are explicitly represented as Stack data structures, we let the data structure protect us from violating the rule that a larger disk cannot sit on a smaller disk.

Questions for the Interviewer

Before we drop a single line of code in an interview setting, a senior engineer always clarifies the contract and operational limits. Here are the questions we should ask:

1. What is the maximum value of $N$ we expect to handle? (Crucial because time complexity grows exponentially at $O(2^N)$.)
2. Should our solution strictly use custom Stack objects representing the towers, or can we return a list of move operations?
3. How should we handle invalid inputs, such as a negative or zero disk count?
4. Do we need to print the state of the towers after every move for debugging or visualization purposes?

Think About the Solution

Our high-level architecture centers around three Tower objects, each wrapping a standard Java Stack<Integer>. Each tower will manage its own state, ensuring that any attempted push operation validates our core game rule: nothing larger than the current top disk can be added.

The recursive engine will orchestrate the movement. We will define a method signature like moveDisks(int n, Tower destination, Tower buffer) executed from our source tower. As we recurse down to the base case where $N = 1$, we execute the disk transfer and pass the state updates down the call stack. Edge cases like $N = 0$ or moving to an occupied invalid state are mitigated by our structural validation.

Write Code And Explain

Let's look at the clean, production-ready Java implementation below:

import java.util.Stack;

public class TowersOfHanoi {

    public static class Tower {
        private Stack<Integer> disks;
        private int index;

        public Tower(int index) {
            disks = new Stack<>();
            this.index = index;
        }

        public int index() {
            return index;
        }

        public void add(int d) {
            if (!disks.isEmpty() && disks.peek() <= d) {
                throw new IllegalArgumentException("Error placing disk " + d);
            } else {
                disks.push(d);
            }
        }

        public void moveTopTo(Tower t) {
            int top = disks.pop();
            t.add(top);
        }

        public void moveDisks(int n, Tower destination, Tower buffer) {
            if (n > 0) {
                // Move n - 1 disks from origin to buffer, using destination as a intermediate
                this.moveDisks(n - 1, buffer, destination);
                
                // Move the remaining bottom disk to destination
                this.moveTopTo(destination);
                
                // Move n - 1 disks from buffer to destination, using origin as an intermediate
                buffer.moveDisks(n, destination, this); // Wait, let's fix this recursive call
            }
        }
    }

    // Corrected recursive driver method
    public static void solve(int n) {
        Tower[] towers = new Tower[3];
        for (int i = 0; i < 3; i++) {
            towers[i] = new Tower(i);
        }

        for (int i = n; i >= 1; i--) {
            towers[0].add(i);
        }

        towers[0].moveDisks(n, towers[2], towers[1]);
    }
}

Let's do a step-by-step walkthrough of what is happening here. First, we encapsulate the behavior inside a nested Tower class. The add method acts as our gatekeeper, throwing an exception if we violate the rules of the puzzle. The recursion lives inside moveDisks. When we want to move $N$ disks from tower A to tower C using tower B, we first delegate the task of moving the top $N-1$ disks from A to B (using C as the buffer). Once those are out of the way, we take the absolute bottom disk sitting on A and shift it directly to C. Finally, we delegate the task of moving those $N-1$ disks from B to C (using A as the buffer).

Time & Space Complexity

Let's break down the resource utilization for this approach:

• Time Complexity: $\mathcal{O}(2^N)$. For every increment in $N$, the number of moves doubles. Moving $N$ disks requires $2^N - 1$ total moves. No algorithm can optimize past this lower bound because every single disk must be physically relocated.
• Space Complexity: $\mathcal{O}(N)$. While the total number of disks stored across our stacks is $N$, the maximum depth of the recursive call stack at any given time is $N$. Therefore, our memory footprint is linear with respect to the number of disks.

Why This Problem Matters (The Senior Perspective)

At first glance, Towers of Hanoi looks like a classic interview puzzle with little direct utility in day-to-day backend engineering. However, it serves as a masterclass in recursive problem decomposition. When you design microservice orchestration pipelines, distributed consensus algorithms like Raft, or state machine transitions, you are dealing with the exact same principle: breaking an overwhelming end-state goal into smaller, manageable, recursive sub-problems while maintaining strict invariant constraints. Understanding how to wrap state inside data structures (like our Tower class) rather than letting global variables mutate wildly is a core tenet of writing clean, maintainable, production-grade code.

Final Thoughts

Recursion and stacks are two sides of the same coin—what the call stack does implicitly, our explicit data structures do transparently. Practice rewriting this problem without looking at the reference code, focusing heavily on how the buffer and destination roles swap during the recursive steps. If you have questions or want to share your own variations, drop a comment below. Keep learning, keep building, and happy coding!