# Design Browser History **Difficulty:** MEDIUM [External](https://leetcode.com/problems/design-browser-history) Canonical: https://scaleengineer.com/dsa/problems/design-browser-history **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream) **Algorithms:** [LRU Cache](https://scaleengineer.com/algorithms/lru-cache) **Data structures:** Array, Linked List, Stack, Doubly-Linked List **Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [Roblox](https://scaleengineer.com/companies/roblox), [Snap](https://scaleengineer.com/companies/snap), [Splunk](https://scaleengineer.com/companies/splunk) --- ## Problem 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 <= 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`. # Approaches ## Using a Dynamic Array (Naive) 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. **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. **Pros:** The implementation is straightforward and easy to understand.; `back` and `forward` operations are very fast, with a constant time complexity. **Cons:** The `visit` operation is inefficient. Removing elements from an `ArrayList` can take linear time with respect to the number of elements being removed, as it requires shifting all subsequent elements. ### Explanation In this implementation, we maintain an `ArrayList` 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 sets `currentIndex` to 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 the `currentIndex`. After clearing, the new URL is added to the end of the list, and `currentIndex` is updated to point to this new last position. - **`back(steps)`**: Moves the `currentIndex` backward by `steps`, but ensures it does not go before the beginning of the list (index 0). The new index is calculated as `max(0, currentIndex - steps)`. - **`forward(steps)`**: Moves the `currentIndex` forward by `steps`, but ensures it does not go past the end of the list. The new index is calculated as `min(history.size() - 1, currentIndex + steps)`. ```java import java.util.ArrayList; import java.util.List; class BrowserHistory { private List 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); } } ``` ### Algorithm - Initialize an `ArrayList` named `history` to store the URLs and an integer `currentIndex` to point to the current page. - **`BrowserHistory(homepage)`**: Add the `homepage` to the `history` list and set `currentIndex` to 0. - **`visit(url)`**: 1. Remove all elements from `history` starting from the index `currentIndex + 1` to the end of the list. This clears the forward history. 2. Add the new `url` to the end of the `history` list. 3. Increment `currentIndex` to point to the newly added URL. - **`back(steps)`**: Calculate the new index by moving `steps` back: `newIndex = max(0, currentIndex - steps)`. Update `currentIndex` to `newIndex` and return the URL at this position. - **`forward(steps)`**: Calculate the new index by moving `steps` forward: `newIndex = min(history.size() - 1, currentIndex + steps)`. Update `currentIndex` to `newIndex` and return the URL at this position. ## Using a Doubly Linked List 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. **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. **Pros:** The `visit` operation 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:** `back` and `forward` operations have a time complexity linear in the number of steps, which is less efficient than the O(1) time of an array-based approach. ### Explanation 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 first `Node` for the homepage and initializes `currentNode` to point to it. - **`visit(url)`**: When a new URL is visited, a new `Node` is created. This new node is linked after the `currentNode`. Specifically, `currentNode.next` is set to the new node, and the new node's `prev` is set to `currentNode`. Finally, `currentNode` is advanced to this new node. This elegantly handles clearing the forward history, as the old forward path from the previous `currentNode` becomes unreachable and is eventually garbage collected. - **`back(steps)`**: To go back, we simply traverse the list backwards by following the `prev` pointers for the specified number of `steps`, stopping if we reach the head of the list. - **`forward(steps)`**: Similarly, to go forward, we traverse the list forwards by following the `next` pointers, stopping if we reach the end of the list. ```java 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; } } ``` ### Algorithm - Define a `Node` class containing a `String url`, a `Node prev` pointer, and a `Node next` pointer. - Maintain a `currentNode` pointer that always points to the current page's node. - **`BrowserHistory(homepage)`**: Create a new `Node` for the `homepage` and set `currentNode` to it. - **`visit(url)`**: 1. Create a new `Node` for the given `url`. 2. Set the `next` pointer of the `currentNode` to this new node. 3. Set the `prev` pointer of the new node to `currentNode`. 4. Update `currentNode` to point to the new node. The old forward history is now disconnected and will be garbage collected. - **`back(steps)`**: Traverse backwards from `currentNode` using the `prev` pointer `steps` times, or until `currentNode.prev` is `null`. - **`forward(steps)`**: Traverse forwards from `currentNode` using the `next` pointer `steps` times, or until `currentNode.next` is `null`. ## Using a Dynamic Array with Logical Sizing 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. **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. **Pros:** Optimal time complexity, with all operations running in O(1) time (amortized for `visit`).; Relatively simple to implement, building on the familiar `ArrayList` data structure. **Cons:** Space complexity can be suboptimal. The `ArrayList` only 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. ### Explanation This approach refines the naive `ArrayList` solution to achieve optimal time complexity. We use an `ArrayList` 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. `current` is set to 0, and `size` is set to 1, indicating a history of one page. - **`visit(url)`**: When visiting a new page, we first advance `current`. Then, we place the new `url` at this new `current` index. If this index is already within the physical bounds of the `ArrayList` (i.e., we are overwriting a previously 'cleared' forward history entry), we use `history.set()`. If it's a new entry at the end, we use `history.add()`. The key step is then updating `size = 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 calculate `current = max(0, current - steps)`. - **`forward(steps)`**: This is also O(1). We calculate `current = min(size - 1, current + steps)`. Note that we use `size - 1` as the upper bound, which correctly respects the logically cleared forward history. ```java import java.util.ArrayList; import java.util.List; class BrowserHistory { private List 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); } } ``` ### Algorithm - Initialize an `ArrayList` `history`, an integer `current` for the current index, and an integer `size` for the logical size of the history. - **`BrowserHistory(homepage)`**: Add `homepage` to `history`, set `current = 0`, and `size = 1`. - **`visit(url)`**: 1. Increment `current`. 2. If `current` is less than the physical size of `history`, overwrite the element at that index: `history.set(current, url)`. 3. Otherwise, if `current` is at the end, add the new URL: `history.add(url)`. 4. Update the logical size: `size = current + 1`. This logically discards the old forward history. - **`back(steps)`**: Update `current = max(0, current - steps)` and return the URL at `history.get(current)`. - **`forward(steps)`**: Update `current = min(size - 1, current + steps)` and return the URL at `history.get(current)`. # Solutions ### Java ```java 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); */ ``` ### CPP ```cpp 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); */ ``` ### Python ```python 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) ```