Design Browser History
Problem
Implement a browser history system that supports visiting new URLs, moving back in history by a given number of steps, and moving forward in history by a given number of steps, returning the current URL after each operation.
- 1 ≤ steps ≤ 100
- 1 ≤ url.length ≤ 20
- url consists of lowercase English letters and '.'
- At most 5000 calls will be made to visit, back, and forward.
Example
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");
browserHistory.visit("facebook.com");
browserHistory.visit("youtube.com");
browserHistory.back(1);
browserHistory.back(1);
browserHistory.forward(1);
browserHistory.visit("linkedin.com");
browserHistory.forward(2);
browserHistory.back(2);
browserHistory.back(7);[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]Start at 'leetcode.com'. Visit 'google.com', 'facebook.com', and 'youtube.com' sequentially, building back history. Back(1) moves from 'youtube.com' to 'facebook.com'. Back(1) moves to 'google.com'. Forward(1) moves to 'facebook.com'. Visit('linkedin.com') clears forward history and sets current to 'linkedin.com'. Forward(2) has no effect since forward history is empty. Back(2) moves back to 'google.com'. Back(7) moves back as far as possible to 'leetcode.com'.
Approach
Straightforward Solution
One could store the entire history in a list and maintain an index pointer for the current page. Moving back or forward would adjust the index accordingly. However, clearing forward history on visit requires slicing or resetting the list, which can be inefficient.
Core Observation
Browser navigation can be modeled as a linear history with a current position, where moving back and forward corresponds to moving along this history. Using two stacks to represent backward and forward history allows efficient simulation of these movements.
Path to Optimal
Using two stacks cleanly separates backward and forward history. The back stack holds pages visited before the current one, and the forward stack holds pages ahead. Visiting a new page pushes the current page onto the back stack and clears the forward stack. Moving back pops from the back stack to the current page and pushes the previous current page onto the forward stack, and vice versa for moving forward. This approach cleanly models browser behavior with O(1) amortized operations per step.
Optimal Approach
Maintain three variables: back_stack, forward_stack, and curr (current page). On visit, push curr to back_stack, update curr, and clear forward_stack. On back, pop from back_stack to curr and push previous curr to forward_stack up to steps times or until back_stack is empty. On forward, pop from forward_stack to curr and push previous curr to back_stack similarly. Return curr after back and forward operations.
Time
O(steps) per back or forward call, O(1) per visit call
Each back or forward operation moves pages between stacks up to the number of steps requested, resulting in O(steps) time. Visit operations perform constant-time stack operations.
Space
O(n)
The space used is proportional to the number of visited pages stored in the back and forward stacks, which can grow linearly with the number of visit calls.
Pattern Spotlight
Simulation (Stateful Stack-Based History Management)
Model bidirectional navigation by maintaining two stacks representing backward and forward history, pushing and popping pages to simulate user navigation efficiently and cleanly.
Solution
| 1 | class BrowserHistory: |
| 2 | |
| 3 | def __init__(self, homepage: str): |
| 4 | self.back_stack = [] |
| 5 | self.forward_stack = [] |
| 6 | self.curr = homepage |
| 7 | |
| 8 | def visit(self, url: str) -> None: |
| 9 | self.back_stack.append(self.curr) |
| 10 | self.curr = url |
| 11 | self.forward_stack = [] |
| 12 | |
| 13 | def back(self, steps: int) -> str: |
| 14 | while steps > 0 and self.back_stack: |
| 15 | self.forward_stack.append(self.curr) |
| 16 | self.curr = self.back_stack.pop() |
| 17 | steps -= 1 |
| 18 | return self.curr |
| 19 | |
| 20 | def forward(self, steps: int) -> str: |
| 21 | while steps > 0 and self.forward_stack: |
| 22 | self.back_stack.append(self.curr) |
| 23 | self.curr = self.forward_stack.pop() |
| 24 | steps -= 1 |
| 25 | return self.curr |
Step-by-Step Solution
Initialize Browser History State with Homepage
| 4 | self.back_stack = [] |
| 5 | self.forward_stack = [] |
| 6 | self.curr = homepage |
Objective
To set up the initial browser state with empty back and forward stacks and the current page set to the homepage.
Key Insight
Starting with empty stacks ensures no backward or forward history exists initially. Setting the current page to the homepage reflects the browser's starting point. This clean separation of state variables simplifies subsequent navigation operations.
Interview Quick-Check
Core Logic
The back and forward stacks represent navigation history before and after the current page, respectively.
State & Boundaries
The current page is stored separately to allow O(1) access and updates during navigation.
Visit a New URL and Reset Forward History
| 9 | self.back_stack.append(self.curr) |
| 10 | self.curr = url |
| 11 | self.forward_stack = [] |
Objective
To record the current page in back history, update the current page to the new URL, and clear forward history.
Key Insight
Visiting a new page invalidates any forward history because the user has branched off the previous forward path. By pushing the current page onto the back stack before updating, the algorithm preserves backward navigation. Clearing the forward stack ensures no stale forward pages remain accessible.
Interview Quick-Check
Core Logic
Pushing the current page onto the back stack preserves the ability to navigate back after visiting a new page.
Common Pitfalls & Bugs
Forgetting to clear the forward stack after visiting a new page leads to incorrect forward navigation.
Move Backward in History Up to Steps
| 14 | while steps > 0 and self.back_stack: |
| 15 | self.forward_stack.append(self.curr) |
| 16 | self.curr = self.back_stack.pop() |
| 17 | steps -= 1 |
| 18 | return self.curr |
Objective
To move back in history by popping pages from the back stack to the current page and pushing the previous current page onto the forward stack, up to the requested number of steps.
Key Insight
Each backward step transfers the current page to the forward stack and replaces it with the most recent page from the back stack. This simulates the browser's back button behavior. The loop stops early if the back stack is empty, ensuring no invalid navigation.
Interview Quick-Check
Core Logic
Moving back involves popping from the back stack to update the current page and pushing the old current page onto the forward stack.
State & Boundaries
The loop condition ensures we do not move back beyond the earliest visited page.
Move Forward in History Up to Steps
| 21 | while steps > 0 and self.forward_stack: |
| 22 | self.back_stack.append(self.curr) |
| 23 | self.curr = self.forward_stack.pop() |
| 24 | steps -= 1 |
| 25 | return self.curr |
Objective
To move forward in history by popping pages from the forward stack to the current page and pushing the previous current page onto the back stack, up to the requested number of steps.
Key Insight
Each forward step transfers the current page to the back stack and replaces it with the most recent page from the forward stack. This simulates the browser's forward button behavior. The loop stops early if the forward stack is empty, preventing invalid navigation.
Interview Quick-Check
Core Logic
Moving forward involves popping from the forward stack to update the current page and pushing the old current page onto the back stack.
State & Boundaries
The loop condition ensures we do not move forward beyond the most recently visited page.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
self.back_stack.append(self.curr)Push the current page onto the back stack before visiting a new URL.
Preserving the current page in back history allows the user to return to it after visiting a new page, maintaining correct navigation order.
self.forward_stack = []Clear the forward stack to discard forward history after visiting a new page.
Visiting a new page invalidates any forward history, so clearing the forward stack prevents incorrect forward navigation.
self.curr = self.back_stack.pop()Pop the most recent page from the back stack and set it as the current page.
This updates the current page to the previous page in history, simulating the back button behavior.
self.curr = self.forward_stack.pop()Pop the most recent page from the forward stack and set it as the current page.
This updates the current page to the next page in history, simulating the forward button behavior.
self.back_stack = []Initialize an empty stack to store backward history.
This stack holds all pages visited before the current page, enabling efficient back navigation.
self.forward_stack = []Initialize an empty stack to store forward history.
This stack holds pages ahead of the current page, enabling efficient forward navigation after moving back.
self.forward_stack.append(self.curr)Push the current page onto the forward stack before moving back.
This preserves the current page in forward history, enabling forward navigation after moving back.
self.back_stack.append(self.curr)Push the current page onto the back stack before moving forward.
This preserves the current page in back history, enabling backward navigation after moving forward.
self.curr = homepageSet the current page to the homepage URL.
The current page variable tracks the active page, allowing O(1) access and updates during navigation.
self.curr = urlUpdate the current page to the newly visited URL.
This reflects the user's navigation to a new page, which becomes the active page.
return self.currReturn the current page after moving back.
Returning the current page provides the updated browser state to the caller.
return self.currReturn the current page after moving forward.
Returning the current page provides the updated browser state to the caller.
while steps > 0 and self.back_stack:Begin a loop to move back up to the requested number of steps.
The loop controls backward navigation, ensuring movement only occurs while steps remain and back history exists.
while steps > 0 and self.forward_stack:Begin a loop to move forward up to the requested number of steps.
The loop controls forward navigation, ensuring movement only occurs while steps remain and forward history exists.
steps -= 1Decrement the remaining steps to move back.
Tracking steps ensures the loop terminates after moving back the requested number of times.
steps -= 1Decrement the remaining steps to move forward.
Tracking steps ensures the loop terminates after moving forward the requested number of times.
Test Your Understanding
Why does using two stacks to represent backward and forward history correctly simulate browser navigation?
Because the back stack stores all pages visited before the current page, and the forward stack stores pages ahead, pushing and popping between these stacks accurately models moving back and forward through history while allowing efficient clearing of forward history on new visits.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Design Browser History from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Design Browser History drill