Free lesson · DSA Mastery - Interview Prep, End to End

Design Browser History

Hard9 min readdsadata-structure-design

Design Browser History

Design Browser History opens the History & Navigation sub-group with a structure modeling forward/back navigation: visit(url) adds a new page (clearing any forward history), back(steps) and forward(steps) move along the history bounded by the ends. A dynamic array with a current-position pointer is the cleanest model - visit truncates everything after the pointer and appends, while back/forward clamp the pointer within bounds. It is a focused application of array-plus-pointer design that mirrors real browser and undo/redo semantics, and a gentle lead-in to the cache designs that follow. We present the array + current-pointer design (canonical) and the doubly-linked-list alternative.

The insight: browser history is a linear sequence with a single "you are here" cursor. Visiting a new page from the middle of history discards the forward pages (you can't redo after a new action) - exactly like undo/redo. An array holding the visited URLs plus an integer current index models this perfectly: visit sets current++, writes the URL there, and conceptually drops everything beyond; back/forward move current by up to steps, clamped to [0, last]. All operations are O(1) except the clamping, which is trivial.

The Problem

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Example 1:

BrowserHistory bh = new BrowserHistory("leetcode.com");
bh.visit("google.com");       // history: [leetcode, google], current = google
bh.visit("facebook.com");     // [leetcode, google, facebook]
bh.visit("youtube.com");      // [leetcode, google, facebook, youtube]
bh.back(1);                    // "facebook.com"
bh.back(1);                    // "google.com"
bh.forward(1);                 // "facebook.com"
bh.visit("linkedin.com");      // clears forward; [leetcode, google, facebook, linkedin]
bh.forward(2);                 // "linkedin.com" (no forward history; clamped)
bh.back(2);                    // "google.com"
bh.back(7);                    // "leetcode.com" (clamped to start)

Constraints:

• 1 <= homepage.length, url.length <= 20
• 1 <= steps <= 100
• At most 5000 calls will be made to visit, back, and forward.

Approaches Overview

The array approach keeps a list of visited URLs and a current index, plus a logical size marking the valid forward extent; visit increments current, writes the URL, and sets size = current + 1 (truncating forward history); back/forward clamp current within [0, size-1] in O(1). The doubly-linked-list approach keeps a node per page with prev/next pointers; visit links a new node and severs forward, back/forward walk pointers (O(steps)). Both model the cursor; the array gives O(1) navigation by clamping the index directly.

Approach 1: Array + Current Index - Canonical

The Idea

Store visited URLs in a list, with current indexing the active page and size marking how many pages are logically valid (forward extent). visit(url): increment current, write url at that position (overwriting any stale forward entry or appending), and set size = current + 1 - this discards forward history. back(steps): current = max(0, current - steps). forward(steps): current = min(size - 1, current + steps). Each navigation returns the URL at current.

Logic Flowchart

graph TD
    A["list = [homepage], current = 0, size = 1"] --> B["visit(url)"]
    B --> C["current++; set list[current] = url; size = current + 1  // truncate forward"]
    D["back(steps)"] --> E["current = max(0, current - steps)"]
    F["forward(steps)"] --> G["current = min(size - 1, current + steps)"]
    E --> H["return list[current]"]
    G --> H
    C --> I["return (no value)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the array browser history. Visiting advances the current index, writes the URL, and truncates forward history; back and forward clamp the current index within the valid range and return the active URL.

Code

class BrowserHistory {
    private final List<String> history = new ArrayList<>();
    private int current = 0;   // index of the active page
    private int size = 1;      // number of logically valid pages (forward extent)

    public BrowserHistory(String homepage) {
        history.add(homepage);
    }

    public void visit(String url) {
        current++;
        if (current < history.size()) history.set(current, url);  // overwrite stale forward slot
        else history.add(url);                                    // or append
        size = current + 1;                                       // forward history cleared
    }

    public String back(int steps) {
        current = Math.max(0, current - steps);                   // clamp to start
        return history.get(current);
    }

    public String forward(int steps) {
        current = Math.min(size - 1, current + steps);            // clamp to last valid
        return history.get(current);
    }
}

// Usage:
// BrowserHistory bh = new BrowserHistory("leetcode.com");
// bh.visit("google.com"); bh.visit("facebook.com"); bh.back(1) -> "facebook.com";
// bh.forward(1) -> "facebook.com" ... bh.back(7) -> "leetcode.com"

This Java code keeps a list of URLs with a current index and a logical size; visit advances current and resets size to clear forward history, while back and forward clamp current within bounds and return the active URL.

Step-by-Step Walkthrough

A frame-by-frame trace on part of the Example:

graph LR
    F0["visit google, facebook, youtube: list=[L,G,F,Y], current=3, size=4"]
    F1["back(1): current=2 → facebook. back(1): current=1 → google"]
    F2["forward(1): current=2 → facebook. visit linkedin: current=3, list[3]=linkedin, size=4 (forward cleared)"]
    F3["forward(2): min(3, 5)=3 → linkedin. back(2): 1 → google. back(7): max(0,-6)=0 → leetcode"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs the history. After visiting three pages, back and forward move the cursor; visiting linkedin clears forward history, so a forward jump clamps to linkedin, and a large back clamps to the homepage.

Result: navigation clamps correctly; back(7) returns "leetcode.com".

Complexity

Time: visit, back, forward all O(1). Space: O(pages visited).

Approach 2: Doubly Linked List - Elegant Alternative

The Idea

Each page is a node with url, prev, and next. Keep a current node pointer. visit(url): create a node, link current.next to it and its prev to current, then move current forward - this severs any old forward chain (the old next becomes unreachable). back(steps): follow prev up to steps times or until the head. forward(steps): follow next up to steps times or until the tail. Navigation is O(steps).

Complexity

Time: visit O(1), back/forward O(steps). Space: O(pages visited).

Complexity Comparison

The array design gives O(1) navigation because moving steps is a single clamped index arithmetic, not a pointer walk. The linked list is conceptually elegant (the forward chain is severed naturally on visit) but navigation is O(steps). Both model the single-cursor linear history; the array's size field cleanly encodes "forward history extent," making truncation and clamping trivial.

Variations & Follow-ups

Why does visit clear forward history, and how does the size field encode that?

Browser (and undo/redo) semantics dictate that taking a new action from a point in the middle of history makes the previously-"forward" pages unreachable - you can't redo after doing something new. So visit must discard everything after the current position. The array models this with a logical size field separate from the underlying list's physical length: after visit, size = current + 1 declares that only positions 0..current are valid, regardless of whether stale URLs still sit physically beyond current in the backing list. forward clamps to size - 1, so it can never reach those stale entries. This "logical size ≤ physical capacity" trick - the same idea as a logical window over a fixed buffer - avoids actually deleting array elements (O(n)) on every visit; you just shrink the valid range to O(1). A later visit overwrites the now-invalid slot.

Why is the array's navigation O(1) while the linked list's is O(steps)?

In the array, the current position is an integer index, and moving steps back or forward is a single arithmetic operation - current ± steps - clamped to the valid range. You don't traverse intermediate pages; you jump directly to the target index and read it. That's O(1) regardless of how many steps. In the doubly linked list, pages are connected only by pointers, so to move steps you must follow prev/next one node at a time, stopping early if you hit an end - O(steps). For this problem steps is at most 100, so both are fast in practice, but the array is asymptotically better for navigation. The trade-off is that the linked list expresses "sever forward history" more naturally (just drop the next pointer), whereas the array needs the explicit size bookkeeping. The array wins on navigation cost; the list wins on conceptual clarity of truncation.

Why clamp rather than reject out-of-range back/forward?

The contract specifies moving at most steps: if you ask to go back 7 but only 3 pages exist behind you, you end at the earliest page, not an error. Clamping implements "at most" directly - back uses max(0, current - steps) so you never go before the homepage, and forward uses min(size - 1, current + steps) so you never pass the latest valid page. This matches real browser behavior (the back button greys out at the start; it doesn't crash) and undo/redo (undo stops at the initial state). Rejecting or throwing would violate the "at most" semantics. Clamping also makes the operations total (always defined) and O(1), since it's just a min/max - no loop to count available steps. The clamp is the precise encoding of the bounded-navigation contract.

How does this structure generalize to undo/redo systems?

Browser history is structurally identical to undo/redo: the history list is the sequence of states (or actions), current is the present state, back is undo, forward is redo, and visit (a new action) clears the redo stack. Many editors implement exactly this - an array of states with a cursor, where performing a new action after some undos truncates the redo branch. The same size-as-logical-extent trick bounds memory and makes truncation O(1). Variations add a capacity cap (keep only the last N states, evicting the oldest - a bounded history, which connects to the cache designs next), or store deltas rather than full states (like Snapshot Array's per-cell changes) to save memory. Recognizing browser history, undo/redo, and bounded action logs as the same array-plus-cursor design lets you implement all of them from one mental template.

What about edge cases?

• Back/forward beyond bounds (Example: back(7)): Clamped to the homepage (index 0).
• Forward with no forward history (after a visit): size - 1 == current, so forward stays put.
• Visit after backing up (Example: visit("linkedin") after backs): Overwrites the stale forward slot and resets size, clearing forward pages.
• Single page (homepage only): Back and forward both clamp to it.
• Repeated visits: Each appends/overwrites and advances the cursor.

Common Interview Pitfalls

• Physically deleting forward entries on visit. O(n) per visit; instead shrink the logical size to truncate in O(1).
• Not clamping navigation. back/forward must move at most steps, clamping to the ends, not erroring.
• Forgetting to reset size on visit. Without it, a later forward could resurrect cleared forward pages.
• Off-by-one in the forward bound. Clamp to size - 1 (last valid index), not size.

Why This Topic Matters

Design Browser History models single-cursor linear navigation with an array plus current index and a logical size: visit advances the cursor and truncates forward history in O(1) by shrinking the valid range, while back/forward clamp the index for O(1) bounded navigation. It teaches the logical-size-over-physical-capacity trick and maps directly onto undo/redo systems - a clean array-plus-pointer design leading into the cache structures.

The next topic, LRU Cache, opens the Cache Design sub-group with one of the most-asked design problems: a fixed-capacity key-value cache that evicts the least recently used entry when full, with both get and put in O(1). The canonical design composes a hash map (key → node, for O(1) lookup) with a doubly linked list ordered by recency (most recent at one end, least recent at the other), so touching an entry moves its node to the front and eviction removes the back node - both O(1). It is the definitive "hash map plus linked list" composition and a rite of passage for technical interviews.

Back to DSA Mastery - Interview Prep, End to End