Design Browser History
MedPrompt
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 thehomepageof the browser.void visit(string url)Visitsurlfrom the current page. It clears up all the forward history.string back(int steps)Movestepsback in history. If you can only returnxsteps in the history andsteps > x, you will return onlyxsteps. Return the currenturlafter moving back in history at moststeps.string forward(int steps)Movestepsforward in history. If you can only forwardxsteps in the history andsteps > x, you will forward onlyxsteps. Return the currenturlafter forwarding in history at moststeps.
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 <= 100homepageandurlconsist of '.' or lower case English letters.- At most
5000calls will be made tovisit,back, andforward.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a dynamic array, like Java's ArrayList, to store the browser history. A separate integer variable acts as a pointer to the current page's index in the array. While back and forward operations are efficient, the visit operation can be slow because it requires clearing the forward history by removing elements from the list.
Algorithm
- Initialize an
ArrayList<String>namedhistoryto store the URLs and an integercurrentIndexto point to the current page. BrowserHistory(homepage): Add thehomepageto thehistorylist and setcurrentIndexto 0.visit(url):- Remove all elements from
historystarting from the indexcurrentIndex + 1to the end of the list. This clears the forward history. - Add the new
urlto the end of thehistorylist. - Increment
currentIndexto point to the newly added URL.
- Remove all elements from
back(steps): Calculate the new index by movingstepsback:newIndex = max(0, currentIndex - steps). UpdatecurrentIndextonewIndexand return the URL at this position.forward(steps): Calculate the new index by movingstepsforward:newIndex = min(history.size() - 1, currentIndex + steps). UpdatecurrentIndextonewIndexand return the URL at this position.
Walkthrough
In this implementation, we maintain an ArrayList<String> to store the sequence of visited URLs and an integer currentIndex to track our position within that list.
- Constructor
BrowserHistory(homepage): Initializes the list with the homepage and setscurrentIndexto 0. visit(url): This is the most performance-critical operation in this approach. When visiting a new URL, all forward history must be cleared. This is achieved by removing all URLs from the list that are located after thecurrentIndex. After clearing, the new URL is added to the end of the list, andcurrentIndexis updated to point to this new last position.back(steps): Moves thecurrentIndexbackward bysteps, but ensures it does not go before the beginning of the list (index 0). The new index is calculated asmax(0, currentIndex - steps).forward(steps): Moves thecurrentIndexforward bysteps, but ensures it does not go past the end of the list. The new index is calculated asmin(history.size() - 1, currentIndex + steps).
import java.util.ArrayList;import java.util.List; class BrowserHistory { private List<String> history; private int currentIndex; public BrowserHistory(String homepage) { history = new ArrayList<>(); history.add(homepage); currentIndex = 0; } public void visit(String url) { // Remove forward history. This is the inefficient part. history.subList(currentIndex + 1, history.size()).clear(); history.add(url); currentIndex++; } public String back(int steps) { currentIndex = Math.max(0, currentIndex - steps); return history.get(currentIndex); } public String forward(int steps) { currentIndex = Math.min(history.size() - 1, currentIndex + steps); return history.get(currentIndex); }}Complexity
Time
- **`visit(url)`**: O(N), where N is the number of elements in the forward history. In the worst case, where the current page is the first one, this is proportional to the total history size. - **`back(steps)`**: O(1), as it only involves arithmetic and a single array access. - **`forward(steps)`**: O(1), for the same reasons as `back`.
Space
O(M), where M is the number of URLs currently in the browser history. The space used is directly proportional to the length of the active history.
Trade-offs
Pros
The implementation is straightforward and easy to understand.
backandforwardoperations are very fast, with a constant time complexity.
Cons
The
visitoperation is inefficient. Removing elements from anArrayListcan take linear time with respect to the number of elements being removed, as it requires shifting all subsequent elements.
This approach models the browser history using a doubly linked list. Each node in the list represents a web page, containing the URL and pointers to the previous (back) and next (forward) pages. This structure is a natural fit for the problem, allowing for efficient visit operations by simply adjusting pointers.
Algorithm
- Define a
Nodeclass containing aString url, aNode prevpointer, and aNode nextpointer. - Maintain a
currentNodepointer that always points to the current page's node. BrowserHistory(homepage): Create a newNodefor thehomepageand setcurrentNodeto it.visit(url):- Create a new
Nodefor the givenurl. - Set the
nextpointer of thecurrentNodeto this new node. - Set the
prevpointer of the new node tocurrentNode. - Update
currentNodeto point to the new node. The old forward history is now disconnected and will be garbage collected.
- Create a new
back(steps): Traverse backwards fromcurrentNodeusing theprevpointerstepstimes, or untilcurrentNode.previsnull.forward(steps): Traverse forwards fromcurrentNodeusing thenextpointerstepstimes, or untilcurrentNode.nextisnull.
Walkthrough
A doubly linked list provides an elegant solution. We define a Node class with fields for the URL, a pointer to the previous node (prev), and a pointer to the next node (next). A single currentNode pointer is maintained to keep track of the current page.
- Constructor
BrowserHistory(homepage): Creates the firstNodefor the homepage and initializescurrentNodeto point to it. visit(url): When a new URL is visited, a newNodeis created. This new node is linked after thecurrentNode. Specifically,currentNode.nextis set to the new node, and the new node'sprevis set tocurrentNode. Finally,currentNodeis advanced to this new node. This elegantly handles clearing the forward history, as the old forward path from the previouscurrentNodebecomes unreachable and is eventually garbage collected.back(steps): To go back, we simply traverse the list backwards by following theprevpointers for the specified number ofsteps, stopping if we reach the head of the list.forward(steps): Similarly, to go forward, we traverse the list forwards by following thenextpointers, stopping if we reach the end of the list.
class BrowserHistory { private class Node { String url; Node prev; Node next; Node(String url) { this.url = url; this.prev = null; this.next = null; } } private Node currentNode; public BrowserHistory(String homepage) { currentNode = new Node(homepage); } public void visit(String url) { Node newNode = new Node(url); currentNode.next = newNode; newNode.prev = currentNode; currentNode = newNode; } public String back(int steps) { while (steps > 0 && currentNode.prev != null) { currentNode = currentNode.prev; steps--; } return currentNode.url; } public String forward(int steps) { while (steps > 0 && currentNode.next != null) { currentNode = currentNode.next; steps--; } return currentNode.url; }}Complexity
Time
- **`visit(url)`**: O(1). Creating a node and re-wiring pointers are constant time operations. - **`back(steps)`**: O(S), where S is the number of `steps`, as it may require traversing S nodes. - **`forward(steps)`**: O(S), where S is the number of `steps`, for the same reason as `back`.
Space
O(M), where M is the number of URLs currently in the browser history. Space is reclaimed for cleared forward history.
Trade-offs
Pros
The
visitoperation is highly efficient, taking constant time O(1).Memory usage is optimal, as parts of the history that are no longer reachable (cleared forward history) can be garbage collected.
It's a very intuitive and natural data structure for this kind of problem.
Cons
backandforwardoperations have a time complexity linear in the number of steps, which is less efficient than the O(1) time of an array-based approach.
This is the most efficient approach, achieving constant time complexity for all operations. It's an optimized version of the array-based solution. Instead of physically removing elements from the array when clearing forward history (which is slow), we use a variable to mark the logical end of the history. New visits simply overwrite the 'dead' part of the array.
Algorithm
- Initialize an
ArrayList<String>history, an integercurrentfor the current index, and an integersizefor the logical size of the history. BrowserHistory(homepage): Addhomepagetohistory, setcurrent = 0, andsize = 1.visit(url):- Increment
current. - If
currentis less than the physical size ofhistory, overwrite the element at that index:history.set(current, url). - Otherwise, if
currentis at the end, add the new URL:history.add(url). - Update the logical size:
size = current + 1. This logically discards the old forward history.
- Increment
back(steps): Updatecurrent = max(0, current - steps)and return the URL athistory.get(current).forward(steps): Updatecurrent = min(size - 1, current + steps)and return the URL athistory.get(current).
Walkthrough
This approach refines the naive ArrayList solution to achieve optimal time complexity. We use an ArrayList<String> to store URLs, an integer current for the current position, and an additional integer size to track the valid, logical size of the history.
- Constructor
BrowserHistory(homepage): Initializes the list with the homepage.currentis set to 0, andsizeis set to 1, indicating a history of one page. visit(url): When visiting a new page, we first advancecurrent. Then, we place the newurlat this newcurrentindex. If this index is already within the physical bounds of theArrayList(i.e., we are overwriting a previously 'cleared' forward history entry), we usehistory.set(). If it's a new entry at the end, we usehistory.add(). The key step is then updatingsize = current + 1. This action logically truncates any old forward history without the expensive cost of actually removing elements from the list.back(steps): This is a simple O(1) operation. We calculatecurrent = max(0, current - steps).forward(steps): This is also O(1). We calculatecurrent = min(size - 1, current + steps). Note that we usesize - 1as the upper bound, which correctly respects the logically cleared forward history.
import java.util.ArrayList;import java.util.List; class BrowserHistory { private List<String> history; private int current; private int size; // Logical size of the history public BrowserHistory(String homepage) { history = new ArrayList<>(); history.add(homepage); current = 0; size = 1; } public void visit(String url) { current++; if (current < history.size()) { history.set(current, url); } else { history.add(url); } size = current + 1; } public String back(int steps) { current = Math.max(0, current - steps); return history.get(current); } public String forward(int steps) { current = Math.min(size - 1, current + steps); return history.get(current); }}Complexity
Time
- **`visit(url)`**: O(1) amortized. `ArrayList.add` has an amortized constant time cost, and `ArrayList.set` is O(1). - **`back(steps)`**: O(1). - **`forward(steps)`**: O(1).
Space
O(N), where N is the total number of URLs ever visited. Because the underlying `ArrayList` never shrinks, its size is determined by the maximum extent the history has ever reached.
Trade-offs
Pros
Optimal time complexity, with all operations running in O(1) time (amortized for
visit).Relatively simple to implement, building on the familiar
ArrayListdata structure.
Cons
Space complexity can be suboptimal. The
ArrayListonly grows and never shrinks, so it may hold references to URLs that are no longer part of the active history, consuming more memory than necessary.
Solutions
Solution
class BrowserHistory { private Deque < String > stk1 = new ArrayDeque <>(); private Deque < String > stk2 = new ArrayDeque <>(); public BrowserHistory ( String homepage ) { visit ( homepage ); } public void visit ( String url ) { stk1 . push ( url ); stk2 . clear (); } public String back ( int steps ) { for (; steps > 0 && stk1 . size () > 1 ; -- steps ) { stk2 . push ( stk1 . pop ()); } return stk1 . peek (); } public String forward ( int steps ) { for (; steps > 0 && ! stk2 . isEmpty (); -- steps ) { stk1 . push ( stk2 . pop ()); } return stk1 . peek (); } } /** * Your BrowserHistory object will be instantiated and called as such: * BrowserHistory obj = new BrowserHistory(homepage); * obj.visit(url); * String param_2 = obj.back(steps); * String param_3 = obj.forward(steps); */class BrowserHistory { public: stack < string > stk1 ; stack < string > stk2 ; BrowserHistory ( string homepage ) { visit ( homepage ); } void visit ( string url ) { stk1 . push ( url ); stk2 = stack < string > (); } string back ( int steps ) { for (; steps && stk1 . size () > 1 ; -- steps ) { stk2 . push ( stk1 . top ()); stk1 . pop (); } return stk1 . top (); } string forward ( int steps ) { for (; steps && ! stk2 . empty (); -- steps ) { stk1 . push ( stk2 . top ()); stk2 . pop (); } return stk1 . top (); } }; /** * Your BrowserHistory object will be instantiated and called as such: * BrowserHistory* obj = new BrowserHistory(homepage); * obj->visit(url); * string param_2 = obj->back(steps); * string param_3 = obj->forward(steps); */class BrowserHistory : def __init__ ( self , homepage : str ): self . stk1 = [] # backward self . stk2 = [] # forward self . visit ( homepage ) def visit ( self , url : str ) -> None : self . stk1 . append ( url ) self . stk2 . clear () def back ( self , steps : int ) -> str : while steps and len ( self . stk1 ) > 1 : self . stk2 . append ( self . stk1 . pop ()) steps -= 1 return self . stk1 [ - 1 ] def forward ( self , steps : int ) -> str : while steps and self . stk2 : self . stk1 . append ( self . stk2 . pop ()) steps -= 1 return self . stk1 [ - 1 ] # Your BrowserHistory object will be instantiated and called as such: # obj = BrowserHistory(homepage) # obj.visit(url) # param_2 = obj.back(steps) # param_3 = obj.forward(steps) ############ class BrowserHistory : def __init__ ( self , homepage : str ): self . his = [ homepage ] self . cur = 0 def visit ( self , url : str ) -> None : while self . his and len ( self . his ) - 1 > self . cur : self . his . pop () self . his . append ( url ) self . cur += 1 def back ( self , steps : int ) -> str : self . cur -= min ( self . cur , steps ) return self . his [ self . cur ] def forward ( self , steps : int ) -> str : self . cur += steps self . cur = min ( self . cur , len ( self . his ) - 1 ) return self . his [ self . cur ] # Your BrowserHistory object will be instantiated and called as such: # obj = BrowserHistory(homepage) # obj.visit(url) # param_2 = obj.back(steps) # param_3 = obj.forward(steps)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.