How to Solve Design Browser History

To solve this, maintain a doubly-linked list or two stacks to efficiently track visited URLs. Use a current pointer to navigate back and forward while updating history correctly. This approach ensures constant-time updates for visit operations and avoids losing forward history when visiting new URLs after going back.

Problem Statement

Design a browser history manager that starts at a homepage and allows visiting new URLs, moving back a number of steps, or moving forward a number of steps. The class should track the current page and maintain the correct forward and backward history as operations are performed.

Implement the BrowserHistory class with the following methods: BrowserHistory(homepage) initializes the object with the homepage. visit(url) navigates to a new URL and clears forward history. back(steps) moves back in history up to the given number of steps. forward(steps) moves forward in history up to the given number of steps.

Examples

Example 1

Input: ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Output: [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com" browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com" browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com" browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com" browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com" browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com" browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com" browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps. browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com" browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Constraints

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage and url consist of '.' or lower case English letters.
• At most 5000 calls will be made to visit, back, and forward.

Solution Approach

Use Doubly-Linked List

Create a doubly-linked list where each node represents a URL. Maintain a current pointer that moves back and forward by following prev and next pointers. Insert new nodes for each visit and cut off forward nodes if visiting after going back.

Use Two Stacks

Maintain one stack for back history and one for forward history. Push the current page to the back stack on visit, clear the forward stack, and move pages between stacks when performing back and forward operations.

Pointer Optimization

Optimize operations by keeping references instead of traversing the list. When visiting, directly attach a new node to the current node and nullify next pointers. For back and forward, move the current pointer while counting steps without extra memory overhead.

Complexity Analysis

Time complexity for visit, back, and forward operations is O(1) per move if using a doubly-linked list with pointers, or O(steps) if using stacks. Space complexity is O(n) for storing up to n visited URLs, regardless of approach.

What Interviewers Usually Probe

• You may be asked to justify linked-list vs stack trade-offs.
• Clarify whether forward history should be cleared on new visits.
• Expect questions about optimizing back and forward operations for large histories.

Common Pitfalls or Variants

Common pitfalls

• Not clearing forward history after a new visit.
• Using a singly-linked list which makes back operation inefficient.
• Incorrectly updating current pointer when moving back or forward multiple steps.

Follow-up variants

• Implement BrowserHistory with circular doubly-linked list for memory reuse.
• Use array-based dynamic structure to simulate stacks for back and forward.
• Extend to multi-tab browsing with separate histories per tab.

How GhostInterview Helps

• Provides step-by-step pointer manipulation walkthroughs.
• Simulates sequences of visit, back, and forward operations to verify correctness.
• Highlights common failure modes like losing forward history or off-by-one pointer errors.

Topic Pages

• Array
• Linked List
• Stack
• Design
• Doubly-Linked List
• Data Stream

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What data structure is best for Design Browser History?

A doubly-linked list or two stacks are optimal, enabling efficient back, forward, and visit operations with pointer manipulation.

How do I handle forward history when visiting a new URL?

Clear all forward nodes or stack entries when a new URL is visited after moving back to ensure correct browser behavior.

Can I use an array instead of a linked list?

Yes, arrays can simulate stacks for back and forward operations, but moving multiple steps may require extra copying or pointer tracking.

Why is pointer manipulation crucial in this problem?

It allows moving back and forward efficiently without traversing the entire history, which is key for large sequences of operations.

What is the complexity of BrowserHistory operations?

Visit is O(1), back and forward are O(steps) if using stacks or O(1) per move using a doubly-linked list with pointers. Space is O(n) for storing URLs.