Code Implementation

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.curr = 0

    def visit(self, url: str) -> None:
        # Discard all forward history
        self.history = self.history[:self.curr + 1]
        self.history.append(url)
        self.curr += 1

    def back(self, steps: int) -> str:
        self.curr = max(0, self.curr - steps)
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        self.curr = min(len(self.history) - 1, self.curr + steps)
        return self.history[self.curr]
      

class BrowserHistory {
public:
    vector<string> history;
    int curr;

    BrowserHistory(string homepage) {
        history.push_back(homepage);
        curr = 0;
    }
    
    void visit(string url) {
        history.resize(curr + 1);
        history.push_back(url);
        curr++;
    }
    
    string back(int steps) {
        curr = max(0, curr - steps);
        return history[curr];
    }
    
    string forward(int steps) {
        curr = min((int)history.size() - 1, curr + steps);
        return history[curr];
    }
};
      

class BrowserHistory {
    private List<String> history;
    private int curr;

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

var BrowserHistory = function(homepage) {
    this.history = [homepage];
    this.curr = 0;
};

BrowserHistory.prototype.visit = function(url) {
    this.history = this.history.slice(0, this.curr + 1);
    this.history.push(url);
    this.curr++;
};

BrowserHistory.prototype.back = function(steps) {
    this.curr = Math.max(0, this.curr - steps);
    return this.history[this.curr];
};

BrowserHistory.prototype.forward = function(steps) {
    this.curr = Math.min(this.history.length - 1, this.curr + steps);
    return this.history[this.curr];
};
      

Problem Description

You are tasked with designing a browser history system that mimics the behavior of a typical web browser's navigation. The system supports the following operations:

• BrowserHistory(homepage): Initializes the browser with the given homepage.
• visit(url): Visits url from the current page. It clears all forward history.
• back(steps): Moves back by steps pages in history. Returns the current page after moving back (cannot go before the homepage).
• forward(steps): Moves forward by steps pages in history. Returns the current page after moving forward (cannot go beyond the most recent page).

Key constraints:

• Each visit operation removes all forward history beyond the current page.
• It is guaranteed that back and forward will not move outside the valid history range.

Thought Process

To simulate browser navigation, we need to keep track of the pages visited and the current position in the history. A naive approach might be to use two stacks: one for back history and one for forward history. However, we can simplify this by using a single list (array) to store the sequence of URLs and an integer pointer to indicate the current page.

The main challenge is handling the visit operation, which should clear all forward history beyond the current page. The back and forward operations just move the current pointer backward or forward within the bounds of the list.

We want each operation to be as efficient as possible, ideally O(1) time, except for the possible truncation of forward history when visiting a new page.

Solution Approach

Let's break down the design and implementation step by step:

1. Data Structures:
   • We use a list (array) history to store the sequence of URLs visited.
   • An integer curr keeps track of the index of the current page.
2. Initialization:
   • When the browser is initialized with a homepage, we add it to the history list and set curr = 0.
3. Visiting a New URL:
   • When visit(url) is called, we need to "forget" all forward history. This is done by truncating the history list to the current index + 1.
   • We then append the new url to history and increment curr.
4. Back Operation:
   • To move back, we decrement curr by steps, but not below 0 (the homepage).
   • Return the page at the new curr index.
5. Forward Operation:
   • To move forward, we increment curr by steps, but not beyond the end of the history list.
   • Return the page at the new curr index.

This approach ensures that all operations are efficient and the browser history behaves as expected.

Example Walkthrough

Let's walk through an example:

• BrowserHistory("leetcode.com"): history = ["leetcode.com"], curr = 0
• visit("google.com"): history = ["leetcode.com", "google.com"], curr = 1
• visit("facebook.com"): history = ["leetcode.com", "google.com", "facebook.com"], curr = 2
• visit("youtube.com"): history = ["leetcode.com", "google.com", "facebook.com", "youtube.com"], curr = 3
• back(1): curr moves to 2, returns "facebook.com"
• back(1): curr moves to 1, returns "google.com"
• forward(1): curr moves to 2, returns "facebook.com"
• visit("linkedin.com"): history = ["leetcode.com", "google.com", "facebook.com", "linkedin.com"], curr = 3 (forward history after facebook.com is cleared)
• forward(2): curr stays at 3, returns "linkedin.com"
• back(2): curr moves to 1, returns "google.com"
• back(7): curr moves to 0, returns "leetcode.com"

This shows how each operation updates the history and current page pointer.

Time and Space Complexity

• Brute-force approach:
  • Using two stacks (back and forward) for history would also be O(1) per operation, but may be less intuitive to implement for this problem.
• Optimized approach (current solution):
  • visit: O(1) amortized (list slicing or truncation is O(1) in most languages, or O(n) worst-case if implemented inefficiently; in practice, it's fast enough).
  • back and forward: O(1), just pointer movement.
  • Space Complexity: O(N), where N is the total number of pages visited (since we store each page in the history list).

Summary

The browser history problem is elegantly solved using a single list (array) to store the URLs and a pointer to track the current position. By truncating the list when visiting a new page, we ensure forward history is always correct. All operations are efficient, simple, and closely mimic real browser behavior, making this a clean and practical design.