1472. Design Browser History

Leetcode #: 1472
Name: Design Browser History
Difficulty: Medium
Url: https://leetcode.com/problems/design-browser-history/

Prompt

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.

Approach

init

Implementing a doubly linked list approach, we want to start off by creating a node with the value of the given homepage. This will be our starting point of our Linked List and we’ll establish it as our head and tail in the beginning. The idea is that we’ll keep updating its tail pointer as we’re visiting more websites or nodes and even if we go back and forward. Technically, we don’t even need the head pointer — we just need a single pointer that we’ll constantly modify and to keep track of where we are currently at in our Linked List (you can call it head or tail or anything else).

visit

We should set our tail’s next pointer to point to a node with the url that the method provides you with. Because we’re utilizing a doubly linked list, we want to set the previous pointer of the next pointer to be the tail. Finally, we want to traverse from the tail to the tail’s next pointer. If you imagine the first iteration of our visit method, our homepageNode will be our starting node or website that will be both the head and tail. Because we’re essentially extending the length of our linked list by 1, this is the reason why we are modifying our tail’s next pointer to be a new node with the provided url and establish its previous pointer as well. Furthermore, we’ll be traversing or updating our tail pointer to be this new node we’ve just created than the homepageNode for the first iteration of the visit method.

back & forward

The logic behind the back & forward method are similar. We’ll be using a while loop for both methods checking as long as their previous & next pointers are not none respectively and if the number of steps provided is greater than 0. For the back method, we want to essentially rewind websites so we would check our tail node’s previous pointer as we would be traversing from our tail to its previous pointer but we want to make sure that the previous pointer is not pointing to null because if it does, then we know that we are at our head or homepageNode node. We want to be decrementing the steps by 1 because we want to be going back x number of steps. Similarly, for the forward method, we want to fast forward x steps and we want to check to make sure that our tail’s next pointer isn’t pointing to null because if it does, then we are at the most updated or latest website. For both our back and forward methods, we want to be returning the website’s value that we eventually end up at once we’ve executed the main body of the logic. Lastly, we are modifying the tail pointer in both of these methods because the tail pointer is going to serve as the pointer that’ll track which website we are currently looking at in our browser.

Code

Python | Time: O(n) | Space: O(n) | n = the total number of nodes

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub