Design Browser History: Stack-Based Navigation

1472. Design Browser History asks you to simulate the back and forward buttons in a web browser. You start on a homepage, you can visit new URLs, and you can navigate backward and forward through your history. The twist that makes it interesting: visiting a new page wipes out any forward history, just like a real browser.

Here is an example of how the operations work:

browser = BrowserHistory("home")
browser.visit("google")
browser.visit("fb")
browser.visit("youtube")
browser.back(1)       # returns "fb"
browser.back(1)       # returns "google"
browser.forward(1)    # returns "fb"
browser.visit("linkedin")  # clears forward history
browser.forward(2)    # returns "linkedin" (can't go further)
browser.back(7)       # returns "home" (stops at the beginning)

Why this problem matters

This is a design problem that tests whether you can pick the right data structure and keep your operations clean. It shows up in interviews because the core mechanic, a list with a pointer that can move in both directions, appears in many real systems: undo/redo stacks in text editors, navigation history in mobile apps, and playlist cursors in media players.

The problem also tests how you handle edge cases with bounded movement. When the user calls back(7) but only has 3 pages of history, your code needs to stop at the beginning without crashing. Getting that clamping logic right is where most bugs hide.

The key insight

You do not need two separate stacks for back and forward. A single list plus a pointer gives you everything. The pointer tracks your current position. Pages before the pointer are your back history. Pages after the pointer are your forward history.

When you visit a new page, you append it right after the current position and delete everything after it. That single operation handles the "clear forward history" requirement. When you go back, you just move the pointer left. When you go forward, you move it right. The list itself never changes during back and forward operations.

The solution

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.curr = 0

    def visit(self, url: str) -> None:
        self.curr += 1
        self.history[self.curr:] = [url]

    def back(self, steps: int) -> str:
        self.curr = max(0, self.curr - steps)
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        self.curr = min(len(self.history) - 1, self.curr + steps)
        return self.history[self.curr]

The __init__ method creates a list with the homepage and sets the pointer to index 0.

visit increments the pointer by one, then uses slice assignment to replace everything from that position onward with the new URL. This simultaneously appends the new page and clears any forward history in a single line.

back moves the pointer left by steps, but clamps it to 0 so it never goes negative. Then it returns the page at the new position.

forward moves the pointer right by steps, but clamps it to the last index so it never goes past the end. Then it returns the page at the new position.

Visual walkthrough

Let's trace through the full example from the problem. Watch how the pointer moves through the list and how visiting a new page clears forward history.

The important moments are Step 8 and Steps 9-10. In Step 8, visiting "linkedin" from index 2 wipes out "youtube" at index 3. In Step 9, trying to go forward 2 steps when already at the end does nothing. In Step 10, trying to go back 7 steps when only 3 steps of history exist clamps the pointer to index 0. These are exactly the edge cases the problem is testing.

Complexity analysis

The list-with-pointer approach gives O(1) back and forward, since you just move an index and clamp it. The visit operation is O(n) in the worst case because the slice assignment may need to delete up to n forward entries. In practice, this is amortized because each page can only be deleted once after being inserted once.

The two-stack approach (one for back history, one for forward history) makes visit O(n) in the worst case too, since you need to clear the forward stack. Back and forward become O(steps) because you pop from one stack and push onto the other one element at a time.

Space is O(n) for both approaches, where n is the total number of pages in history at any point.

The building blocks

1. List with a pointer (bounded cursor)

The pattern of maintaining a position within a list and moving it left or right appears in many problems. The key detail is clamping the pointer so it stays in bounds:

self.curr = max(0, self.curr - steps)
self.curr = min(len(self.history) - 1, self.curr + steps)

This max/min clamping pattern replaces verbose if-else chains. Instead of checking whether you have enough steps of history and handling the edge case separately, you compute the target index and clamp it in one expression.

2. Slice assignment for truncation

Python's slice assignment lets you replace a portion of a list in a single operation. When you write self.history[self.curr:] = [url], you are saying "replace everything from index curr to the end with this one element."

self.history[self.curr:] = [url]

This is equivalent to deleting self.history[self.curr:] and then appending url, but it does both atomically. You avoid the bug where you forget to clear forward history before appending.

3. State encapsulation

The entire browser history is captured by two pieces of state: the list and the pointer. Every operation is a simple transformation of these two values. There are no auxiliary data structures, no caches to invalidate, no synchronization between separate components. This simplicity is what makes the solution easy to reason about and hard to get wrong.

self.history = [homepage]
self.curr = 0

Edge cases

• back(steps) where steps exceeds history length. The pointer should stop at index 0, not go negative. The max(0, ...) clamp handles this.
• forward(steps) where steps exceeds forward history. The pointer should stop at the last index. The min(len - 1, ...) clamp handles this.
• visit after going back. This must clear all forward history. If you are at index 1 with 5 pages in the list, visiting a new page should leave only 3 pages: indices 0, 1, and the new page at index 2.
• Multiple visits without any back/forward. The pointer advances with each visit. No forward history exists, so nothing gets cleared. The list just grows.
• back(0) or forward(0). Moving zero steps should return the current page without changing anything. The clamping logic handles this correctly since curr - 0 = curr.

From understanding to recall

The list-with-pointer approach is simple, but the details matter. The slice assignment for clearing forward history, the max/min clamping for bounded movement, the pointer increment before the slice assignment in visit. These are small things, but getting any one of them wrong breaks the solution on specific test cases.

Spaced repetition drilling is the way to lock in these details. You write the BrowserHistory class from scratch at increasing intervals until the clamping expressions and the slice assignment are second nature. When a design problem asks you to implement navigation with bounded movement, the code flows without hesitation. CodeBricks breaks the solution into its reusable pieces and drills them independently so the pattern sticks.

Related posts

• Min Stack - Another design problem where you maintain auxiliary state alongside a primary data structure, keeping all operations O(1)
• Implement Queue Using Stacks - A design problem where the choice of data structure determines the complexity of every operation
• LRU Cache - The classic design problem that combines a hash map with a doubly linked list for O(1) operations