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.
This approach involves using a list (or similar data structure) to keep track of the pages visited. We use an index to keep track of the current page. Visiting a new page from the current page will truncate the list beyond the current index before adding the new page. Moving back or forward adjusts the index within the bounds of the list.
In this implementation, the 'history' list keeps all the visited pages. 'current' is an integer that marks our current position in the history. When we visit a new URL, the function slices the list up to 'current' and appends the new URL, making sure to remove any forward history. The 'back' and 'forward' functions only adjust the current position and ensure it is within valid bounds.
Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing.
Space Complexity: O(n), where n is the number of URLs stored in history.
This approach uses two stacks: one to store backward paths and another to store forward paths. The current page is not stored in the stack, but rather observed as the topmost element of the backward stack. The back function pops elements from the backward stack to the forward stack as necessary, and the forward function performs the opposite action. This effectively mimicks the process of moving through the history as we go back and forth.
In this Python solution, we use back_stack and forward_stack to keep track of visited pages. 'visit': Pushes the current page to back_stack and resets forward_stack. 'back': Pops pages from back_stack to forward_stack up to steps. 'forward': Pops pages from forward_stack back to back_stack up to steps.
Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks.
Space Complexity: O(n) for maintaining stacks with n pages.
We can use two stacks, stk1 and stk2, to store the back and forward pages, respectively. Initially, stk1 contains the homepage, and stk2 is empty.
When calling visit(url), we add url to stk1 and clear stk2. The time complexity is O(1).
When calling back(steps), we pop the top element from stk1 and push it to stk2. We repeat this operation steps times until the length of stk1 is 1 or steps is 0. Finally, we return the top element of stk1. The time complexity is O(steps).
When calling forward(steps), we pop the top element from stk2 and push it to stk1. We repeat this operation steps times until stk2 is empty or steps is 0. Finally, we return the top element of stk1. The time complexity is O(steps).
The space complexity is O(n), where n is the length of the browsing history.
| Approach | Complexity |
|---|---|
| Approach Using a List | Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing. |
| Approach Using Two Stacks | Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks. |
| Two Stacks | — |
| 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 |
Design Browser History - Leetcode 1472 - Python • NeetCodeIO • 30,276 views views
Watch 9 more video solutions →Practice Design Browser History with our built-in code editor and test cases.
Practice on FleetCode