Design Browser History — Stack-Based Navigation

Problem Statement#

Implement a browser history system: BrowserHistory(homepage) initialises at the homepage; visit(url) navigates to a new URL, clearing all forward history; back(steps) moves back up to steps pages and returns the current URL; forward(steps) moves forward up to steps pages and returns the current URL.

Constraints:

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

Input:  visit("leetcode.com"), visit("google.com"), back(1), back(1)
Output: "leetcode.com", "google.com"

Input:  visit("a.com"), visit("b.com"), visit("c.com"), back(2), forward(5)
Output: "a.com", "c.com"

Why This Problem Matters#

Browser navigation is one of the most universally understood UI patterns—and it maps directly to a two-stack or array-with-pointer data structure. Undo/redo functionality in text editors, IDEs, and design tools uses the same mechanism. At Amazon, undo history in Kindle highlights and at Google in Docs both implement variants of this design.

This problem is asked in FAANG interviews because it tests your ability to model a familiar user-facing feature with the right data structure. The naive approach of using two explicit stacks works but requires O(N) space for forward history that gets discarded on visit. The optimal array-with-pointer approach avoids allocation overhead by truncating in place.

Understanding this design also leads naturally to discussions about cursor-based navigation, command patterns in GUI frameworks, and immutable history for debugging.

The Core Insight#

Use a single array (list) and an integer index curr pointing to the current page. visit(url) truncates the array to curr + 1 (clearing forward history) then appends the new URL and advances curr. back(steps) decrements curr by steps clamped to 0. forward(steps) increments curr by steps clamped to len(history) - 1.

This gives O(1) navigation (back and forward are index arithmetic) and O(N) for visit in the worst case due to truncation, though amortised it is O(1). No separate forward stack is needed because the unused tail of the array implicitly serves that purpose until the next visit call truncates it.

Visual Dry Run#

Solution (Optimal)#

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.idx = 0
 
    def visit(self, url: str) -> None:
        self.history = self.history[:self.idx + 1]
        self.history.append(url)
        self.idx += 1
 
    def back(self, steps: int) -> str:
        self.idx = max(0, self.idx - steps)
        return self.history[self.idx]
 
    def forward(self, steps: int) -> str:
        self.idx = min(len(self.history) - 1, self.idx + steps)
        return self.history[self.idx]

class BrowserHistory {
    constructor(homepage) {
        this.h = [homepage];
        this.i = 0;
    }
 
    visit(url) {
        this.h = this.h.slice(0, this.i + 1);
        this.h.push(url);
        this.i++;
    }
 
    back(steps) {
        this.i = Math.max(0, this.i - steps);
        return this.h[this.i];
    }
 
    forward(steps) {
        this.i = Math.min(this.h.length - 1, this.i + steps);
        return this.h[this.i];
    }
}

Time: O(N) for visit due to truncation in the worst case; O(1) for back and forward
Space: O(N) — one entry per visited page retained in the history array

Common Mistakes#

• Forgetting to truncate the array on visit—without this, forward can navigate to pages visited before a new branch was taken
• Not clamping idx to 0 in back or to len - 1 in forward, causing index out of bounds
• Using two separate stacks (back stack and forward stack)—correct but requires additional stack manipulation on every visit
• Returning None instead of self.history[self.idx] from back and forward
• Off-by-one in truncation: history[:idx + 1] keeps the current page, history[:idx] would remove it

Interview Tips#

• The two-stack approach is a valid alternative: on visit, push to back stack and clear forward stack; on back, move top of back to front of forward; on forward, reverse
• The array-with-pointer approach is cleaner and avoids explicit stack manipulation—present both and explain why you prefer the array approach
• Mention real-world generalisations: undo/redo in text editors uses this exact pattern; the "command pattern" in GUI frameworks adds reversal logic to each action
• For the follow-up about doubly linked list: each page is a node with prev and next pointers; this avoids the O(N) slice overhead on visit

Follow-up Questions#

• How would you implement this with a doubly linked list instead of an array? (Each node has prev/next; visit creates a new node, severs the forward chain)
• How would you support tab groups where each tab has its own history? (One BrowserHistory instance per tab, managed by a Tab manager)
• How would you persist history across browser restarts? (Serialize the array to local storage or a file)
• How would you support a canGoBack() and canGoForward() method? (idx > 0 and idx < len(history) - 1)
• What is the space complexity if the user visits 10000 unique URLs? (O(N) for N unique pages—one entry per visit)

Key Takeaways#

• A single array with an integer curr index models browser navigation without two separate stacks
• visit(url) truncates to history[:curr+1] then appends—this is the critical operation that clears forward history
• back(steps) and forward(steps) clamp the index with max(0, ...) and min(len-1, ...) to prevent out-of-bounds
• The two-stack approach is equivalent but requires more code; the array approach is interview-preferred
• This same pattern implements undo/redo in text editors, design tools, and any command-history system
• Truncation on visit is O(N) in the worst case but O(1) amortised; for truly O(1) visit, use a doubly linked list and sever the forward chain
• Always return history[curr] from back and forward, not the new curr index