Leetcode #1472: Design Browser History

Link to the problem
Design Browser History

Thought Process

We want to support back & forward operations.

Back Operation
Say you visit a website A. Then got to B, C, and D in the order. If you go back, you will be at C. Go back further, you will be at B, and if you go back again, you will reach A.
Thing to note is that the order of websites totally reversed when going back compared to the order in which you visited them. So certainly we need a stack data structure for the back operation which will store the history.

Forward Operation
Say you visit websites in order A, B, C, D. You go back in order C, B, A. Now you are at A. Now if you move forward, you should be able to get to B. Forward again, you should be at C, and one forward should take you to D.
The order of website when going in forward direction is exact opposite of order in which we visited the websites when moving in the backward direction from D. This suggests that we need another stack to store the websites when we go in backward direction.

Leetcode #1472: Design Browser History | Leetcode | Problem Solving | Coding Interview
Leetcode #1472: Design Browser History – Diagram to assist visualization

Algorithm

  1. Maintain two stacks, one for backward direction and another for forward.
  2. Whenever visiting a new website, simply push the current website on the stack for backward direction. Clear the stack for forward direction because from a new website, you can not go forward any further.
  3. When going in a backward direction, push the current website on a stack for the forward direction.
  4. When going in a forward direction, push the current website on a stack for backward direction.

Code

class BrowserHistory {
stack<string> history;
stack<string> future;
string currentWebsite;
void clearForwardStack() {
future = stack<string>();
}
void goBackOneStep() {
if (!history.empty()) {
future.push(currentWebsite);
currentWebsite = history.top();
history.pop();
}
}
void goForwardOneStep() {
if (!future.empty()) {
history.push(currentWebsite);
currentWebsite = future.top();
future.pop();
}
}
public:
BrowserHistory(string homepage) {
currentWebsite = homepage;
clearForwardStack();
}
void visit(string url) {
history.push(currentWebsite);
currentWebsite = url;
clearForwardStack();
}
string back(int steps) {
while(steps > 0) {
goBackOneStep();
steps--;
}
return currentWebsite;
}
string forward(int steps) {
while(steps > 0) {
goForwardOneStep();
steps--;
}
return currentWebsite;
}
};
view raw Leetcode_1472.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget to like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #155: Min Stack


Related Posts


One thought on “Leetcode #1472: Design Browser History

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s