### Leetcode #1472: Design Browser History

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.

### 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 history; stack future; string currentWebsite; void clearForwardStack() { future = stack(); } 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

## One thought on “Leetcode #1472: Design Browser History”

1. Anonymous says:

Very well delivered…

Like