# Design Browser History LeetCode Solution

Difficulty Level Medium
RoboloxViews 1992

## Problem Statement

Design Browser History LeetCode Solution – You have a browser with 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`.
```Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
Output:

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"```

## Explanation

Looking at the constraints of adding and removing elements (web page being visited in this case) we can come up with a data structure which is :

1. Ordered
2. Keeps track of its next value and previous value ( For forwarding and backward operation )
3. Easy to append elements at the top ( For visit operation )

So there is one data structure that can fulfill all these i.e Doubly Linked List.

So we create a doubly linked list whose head will always point to the current page at which the browser is.

Garbage collector/ARC will only free memory when nothing is pointing to a particular memory. It doesn’t require that memory not to point to another memory, that’s fine. It just requires, that there should not be any reference to that memory [to be collected/freed].

But in this case of a doubly-linked list, if we do not make the previous ref as (week reference), a deadlock might occur.

A <—> B [removing point] <—> C <—> D <—> E

after this also

C <—> D <—> E, this will exist

## Code

### C++ Code for Design Browser History

```class BrowserHistory {
public:
string stack[5005];
int p, t;	// current pointer, stack's top

BrowserHistory(string homepage) {
stack[p = t = 0] = homepage;
}

void visit(string url) {
stack[t = ++p] = url;
}

string back(int steps) {
return stack[p = max(0, p-steps)];
}

string forward(int steps) {
return stack[p = min(t, p+steps)];
}
};```

### Java Code for Design Browser History

```class BrowserHistory {

public class Node{
String url;
Node next, prev;
public Node(String url) {
this.url = url;
next = null;
prev = null;
}
}

public BrowserHistory(String homepage) {
}

public void visit(String url) {
Node node = new Node(url);
curr.next = node;
node.prev = curr;
curr = node;
}

public String back(int steps) {
while (curr.prev != null && steps-- > 0) {
curr = curr.prev;
}
return curr.url;
}

public String forward(int steps) {
while (curr.next != null && steps-- > 0) {
curr = curr.next;
}
return curr.url;
}
}```

O(N)

O(N)

Translate »