Design Browser History

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.

Examples

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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"

Solution

Method 1 – Array with Pointer

Intuition

To efficiently manage browser history, we use a list to store visited URLs and a pointer to track the current page. When visiting a new URL, we remove all forward history and add the new URL. The pointer always indicates the current page, allowing quick back and forward navigation.

Approach

Use a list to store the history of URLs.
Maintain an integer pointer for the current position in history.
On visit, remove all URLs after the current pointer and append the new URL.
On back, move the pointer left by up to steps, but not past the first URL.
On forward, move the pointer right by up to steps, but not past the last URL.
Return the URL at the current pointer after each operation.

Complexity

⏰ Time complexity: O(1) for visit, back, and forward, as all operations are direct list and pointer manipulations.
🧺 Space complexity: O(n), where n is the number of visited URLs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class BrowserHistory {
    vector<string> history;
    int pos;
public:
    BrowserHistory(string homepage) {
        history.push_back(homepage);
        pos = 0;
    }
    void visit(string url) {
        history.resize(pos + 1);
        history.push_back(url);
        pos++;
    }
    string back(int steps) {
        pos = max(0, pos - steps);
        return history[pos];
    }
    string forward(int steps) {
        pos = min((int)history.size() - 1, pos + steps);
        return history[pos];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class BrowserHistory {
    private final List<String> history = new ArrayList<>();
    private int pos = 0;
    public BrowserHistory(String homepage) {
        history.add(homepage);
    }
    public void visit(String url) {
        while (history.size() > pos + 1) history.remove(history.size() - 1);
        history.add(url);
        pos++;
    }
    public String back(int steps) {
        pos = Math.max(0, pos - steps);
        return history.get(pos);
    }
    public String forward(int steps) {
        pos = Math.min(history.size() - 1, pos + steps);
        return history.get(pos);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class BrowserHistory:
    def __init__(self, homepage: str) -> None:
        self.history: list[str] = [homepage]
        self.pos: int = 0
    def visit(self, url: str) -> None:
        self.history = self.history[:self.pos + 1]
        self.history.append(url)
        self.pos += 1
    def back(self, steps: int) -> str:
        self.pos = max(0, self.pos - steps)
        return self.history[self.pos]
    def forward(self, steps: int) -> str:
        self.pos = min(len(self.history) - 1, self.pos + steps)
        return self.history[self.pos]

Problem#

Examples#

Solution#

Method 1 – Array with Pointer#

Intuition#

Approach#

Complexity#

Code#