Design Browser History

MediumDesign · Array / Stack🧩 Data Structure Design LeetCode #1472 ↗Updated Oct 30, 2026

Problem

Model a single browser tab. BrowserHistory(homepage) opens the tab; visit(url) goes to a new page and discards all forward history; back(steps) / forward(steps) move at most steps pages (stopping at either end) and return the URL now shown.

Inputhome; visit a, b, c; back(1)Output"b"

Inputback(1); forward(1)Output"a", "b"

Inputvisit d; forward(2); back(9)Output"d", "home"

1 ≤ url length ≤ 20 · 1 ≤ steps ≤ 100 · ≤ 5000 calls in total

Try it yourself

Java

class BrowserHistory {
    public BrowserHistory(String homepage) {
        
    }

    public void visit(String url) {
        
    }

    public String back(int steps) {
        
    }

    public String forward(int steps) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

History is just an array with a cursor. A new visit does not need to delete the forward pages — overwrite the next slot and move a last boundary so stale pages become unreachable.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceTwo Stacks (Back / Forward)

Time visit O(1)*, back/forward O(steps)Space O(n)

Pages behind us sit on backSt, pages ahead on fwdSt. Each step pops one stack and pushes the current page onto the other; visit clears fwdSt.

Java

class BrowserHistory {
    private final Deque<String> backSt = new ArrayDeque<>(), fwdSt = new ArrayDeque<>();
    private String cur;
    public BrowserHistory(String homepage) { cur = homepage; }
    public void visit(String url) {
        backSt.push(cur);
        cur = url;
        fwdSt.clear(); // a new branch kills forward history
    }
    public String back(int steps) {
        while (steps-- > 0 && !backSt.isEmpty()) { fwdSt.push(cur); cur = backSt.pop(); }
        return cur;
    }
    public String forward(int steps) {
        while (steps-- > 0 && !fwdSt.isEmpty()) { backSt.push(cur); cur = fwdSt.pop(); }
        return cur;
    }
}

Intuitive, but navigation walks page by page.

BetterArrayList + Index, Truncate on Visit

Time visit O(f), back/forward O(1)Space O(n)

Keep pages in a list with index cur; back/forward become clamped index jumps. visit first deletes the f pages after cur, then appends.

Java

class BrowserHistory {
    private final List<String> history = new ArrayList<>();
    private int cur = 0;
    public BrowserHistory(String homepage) { history.add(homepage); }
    public void visit(String url) {
        history.subList(cur + 1, history.size()).clear(); // drop forward pages
        history.add(url);
        cur++;
    }
    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return history.get(cur);
    }
    public String forward(int steps) {
        cur = Math.min(history.size() - 1, cur + steps);
        return history.get(cur);
    }
}

O(1) navigation; visit pays for physically deleting forward pages.

OptimalArrayList + cur & last (Overwrite)

Time O(1) all ops*Space O(n)

Track cur (shown page) and last (end of valid history). visit overwrites slot cur+1 and sets last = cur; slots beyond last are unreachable garbage.

Java

class BrowserHistory {
    private final List<String> pages = new ArrayList<>();
    private int cur = 0, last = 0;
    public BrowserHistory(String homepage) { pages.add(homepage); }
    public void visit(String url) {
        if (++cur < pages.size()) pages.set(cur, url); // reuse a stale slot
        else pages.add(url);
        last = cur; // forward history is now unreachable
    }
    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return pages.get(cur);
    }
    public String forward(int steps) {
        cur = Math.min(last, cur + steps);
        return pages.get(cur);
    }
}

Every op O(1) — nothing is ever deleted. (*amortised list growth)

At a glance

Level	Approach	Time	Space
Brute Force	Two Stacks (Back / Forward)	`visit O(1)*, back/forward O(steps)`	`O(n)`
Better	ArrayList + Index, Truncate on Visit	`visit O(f), back/forward O(1)`	`O(n)`
Optimal	ArrayList + cur & last (Overwrite)	`O(1) all ops*`	`O(n)`

Common pitfalls

Forgetting to discard forward history on visit.
Optimal: clamping forward to size()-1 reaches stale pages.
Not clamping at the homepage / newest page.

Interview tips

Clarify: does visit always add a new entry? (Yes.)
Start with two stacks, then switch to an indexed array.
A doubly linked list also works, but moves cost O(steps).

Pattern

Array + cursor with logical size → undo/redo, back/forward navigation, editor history.

My notes saved in this browser