Understanding the Problem

We need to simulate exactly how browser navigation works. You maintain a history of pages you've visited, and you can move backward and forward through that history. The critical behavior is what happens when you visit a new page while you're somewhere in the middle of your history: all the forward history gets wiped out.

Picture it like this. You visit pages A, B, C, D, then go back twice to B. Now you visit E. At this point, C and D are gone forever. Your history is A, B, E, and there's nothing to move forward to. This "clear forward history on visit" behavior is the core design challenge.

The question boils down to: what data structure lets us efficiently append, truncate forward entries, and move a pointer back and forth?

Key Constraints:

1 <= steps <= 100 -> Steps are small, so even a loop-based pointer adjustment is fine. No need for O(1) jump tricks.
At most 5000 calls to visit, back, and forward -> Very small number of operations. Any O(n) approach per call works comfortably.
URL lengths are at most 20 characters -> Memory is not a concern. Storing all visited URLs is cheap.

Approach 1: Doubly Linked List

Intuition

The most natural mental model for browser history is a chain of nodes where you can move forward and backward, exactly like a doubly linked list. Each node stores a URL, and you keep a pointer to your current node. Going back means following the prev pointer, going forward means following the next pointer, and visiting a new page means creating a new node after the current one and severing everything that came after.

This mirrors the real-world metaphor perfectly. But it comes with overhead: creating node objects, managing pointers, and dealing with garbage collection. For a problem like this, it works, but it's heavier than necessary.

Algorithm

Create a doubly linked list node class with url, prev, and next fields.
Initialize the list with a single node containing the homepage. Set current to this node.
On visit(url), create a new node, set current.next to the new node and the new node's prev to current. Move current to the new node. This automatically discards all forward history because nothing points to the old next chain anymore.
On back(steps), move current backward by following prev pointers up to steps times, stopping if prev is null.
On forward(steps), move current forward by following next pointers up to steps times, stopping if next is null.

Example Walkthrough

1Constructor: single node "leetcode.com", current points here

leetcode.com

current

null

1/10

Code

Complexity Analysis

Time Complexity: O(steps) for back and forward, O(1) for visit. Back and forward traverse the linked list one node at a time, up to steps nodes. Visit just creates a node and updates two pointers.
Space Complexity: O(n) where n is the total number of visit calls. Each visit creates a new node. Old forward nodes may be garbage collected, but in the worst case we store all visited URLs.

The linked list approach works but traverses nodes one at a time during back and forward. What if we could avoid node-by-node traversal using a simpler, contiguous data structure?

Approach 2: Array with Pointer (Optimal)

Intuition

Instead of a linked list, use a simple dynamic array (list) and an integer index pointing to the current page. The array stores URLs in visit order, and the index tells us where we are.

The key insight is how to handle "clear forward history." When we visit a new page from the middle of the history, we don't need to actually delete elements from the array. We just place the new URL at position current + 1 and update a boundary variable that marks the last valid index. Anything beyond that boundary is dead history, invisible to back and forward.

This gives us O(1) for all three operations: visit just writes to an index and updates two integers, back and forward just do arithmetic on the current pointer.

Why does this work?

The array acts as a "virtual" history where the last variable serves as a soft boundary. Instead of physically removing forward pages (which would require shifting elements or shrinking the array), we just ignore them by capping forward at last. When a new page is visited, it overwrites whatever was at current + 1, and last moves to match. This is essentially the same trick used in array-based stacks where "popping" just decrements a size counter without clearing memory.

The max and min clamping in back and forward elegantly handles the "can only go x steps" requirement without needing any conditional logic or loops. If you request 100 steps back but you're only at index 2, max(0, 2 - 100) = 0 takes you to the homepage.

Algorithm

Initialize an array with the homepage at index 0. Set current = 0 and last = 0 (the index of the last valid page).
On visit(url), increment current by 1. If current equals the array size, append the URL. Otherwise, overwrite the URL at current. Set last = current to invalidate all forward history.
On back(steps), set current = max(0, current - steps). Return the URL at the new current.
On forward(steps), set current = min(last, current + steps). Return the URL at the new current.

Example Walkthrough

1Constructor: history=["leetcode.com"], current=0, last=0

last

leetcode.com

current

1/10

Code

Complexity Analysis

Time Complexity: O(1) for all three operations. Visit writes to one array position and updates two integers. Back and forward each do a single subtraction/addition and a max/min comparison. No loops, no traversals.
Space Complexity: O(n) where n is the total number of visit calls. We store up to n URLs in the array. The array may contain some stale entries beyond last, but the total size never exceeds the number of visits plus one.

Design Browser History

Understanding the Problem

Key Constraints:

Approach 1: Doubly Linked List

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Array with Pointer (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium