Watch 10 video solutions for Design Browser History, a medium level problem involving Array, Linked List, Stack. This walkthrough by NeetCodeIO has 30,276 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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"]
Explanation:
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 <= 201 <= url.length <= 201 <= steps <= 100homepage and url consist of '.' or lower case English letters.5000 calls will be made to visit, back, and forward.Problem Overview: Design a browser history system that supports visiting new URLs and navigating backward or forward through previously visited pages. The structure must maintain order and correctly discard forward history when a new page is visited after moving back.
Approach 1: Using a List with Current Pointer (O(1) average per operation, O(n) space)
This approach stores all visited URLs in a dynamic array and maintains an index pointing to the current page. When you call visit(url), increment the pointer, overwrite any forward history, and append the new page if needed. The back(steps) operation moves the pointer left using max(0, current - steps), while forward(steps) moves it right but never past the last valid index. The key insight is that browser navigation behaves like moving a cursor in a sequence. This solution is easy to implement and relies only on an array and index arithmetic.
Approach 2: Using Two Stacks (O(1) per operation, O(n) space)
This method models browser navigation using two stacks: a back stack and a forward stack. The current page sits between them. When visiting a new page, push the current page onto the back stack and clear the forward stack because future pages are no longer reachable. For back(steps), repeatedly push the current page onto the forward stack and pop from the back stack. For forward(steps), do the reverse. This approach mirrors how many real browsers manage navigation history and directly uses the LIFO behavior of a stack. It is conceptually clean and common in system design interviews.
Both approaches represent the browsing sequence as a linear structure with a movable pointer. The list-based approach keeps everything in one container, while the stack-based solution explicitly separates backward and forward navigation states. The behavior is closely related to a doubly-linked list where each node has previous and next references.
Recommended for interviews: The list + pointer approach is usually the fastest to implement and keeps each operation constant time with minimal code. Interviewers also appreciate the two-stack design because it clearly models browser navigation logic. Demonstrating the list approach first shows you understand the state transitions, while presenting the stack approach highlights deeper understanding of stack-based navigation systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| List with Current Pointer | O(1) per operation | O(n) | Best for simple implementation using array and index tracking |
| Two Stacks | O(1) per operation | O(n) | When modeling browser navigation explicitly with back and forward stacks |