1472. Design Browser History - Explanation

1. Two Stacks

class BrowserHistory:

    def __init__(self, homepage: str):
        self.back_history = [homepage]
        self.front_history = []

    def visit(self, url: str) -> None:
        self.back_history.append(url)
        self.front_history = []

    def back(self, steps: int) -> str:
        while steps and len(self.back_history) > 1:
            self.front_history.append(self.back_history.pop())
            steps -= 1
        return self.back_history[-1]

    def forward(self, steps: int) -> str:
        while steps and self.front_history:
            self.back_history.append(self.front_history.pop())
            steps -= 1
        return self.back_history[-1]

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for each $visit()$ function call.
- $O(min(n, steps))$ time for each $back()$ and $forward()$ function calls.
Space complexity: $O(m * n)$

Where $n$ is the number of visited urls, $m$ is the average length of each url, and $steps$ is the number of steps we go forward or back.

2. Dynamic Array

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.cur = 0

    def visit(self, url: str) -> None:
        self.cur += 1
        self.history = self.history[:self.cur]
        self.history.append(url)

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

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

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(n)$ time for each $visit()$ function call.
- $O(1)$ time for each $back()$ and $forward()$ function calls.
Space complexity: $O(m * n)$

Where $n$ is the number of visited urls and $m$ is the average length of each url.

3. Dynamic Array (Optimal)

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.cur = 0
        self.n = 1

    def visit(self, url: str) -> None:
        self.cur += 1
        if self.cur == len(self.history):
            self.history.append(url)
            self.n += 1
        else:
            self.history[self.cur] = url
            self.n = self.cur + 1

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

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

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for each $visit()$ function call.
- $O(1)$ time for each $back()$ and $forward()$ function calls.
Space complexity: $O(m * n)$

Where $n$ is the number of visited urls and $m$ is the average length of each url.

4. Doubly Linked List

class ListNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class BrowserHistory:

    def __init__(self, homepage: str):
        self.cur = ListNode(homepage)

    def visit(self, url: str) -> None:
        self.cur.next = ListNode(url, self.cur)
        self.cur = self.cur.next

    def back(self, steps: int) -> str:
        while self.cur.prev and steps > 0:
            self.cur = self.cur.prev
            steps -= 1
        return self.cur.val

    def forward(self, steps: int) -> str:
        while self.cur.next and steps > 0:
            self.cur = self.cur.next
            steps -= 1
        return self.cur.val

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for each $visit()$ function call.
- $O(min(n, steps))$ time for each $back()$ and $forward()$ function calls.
Space complexity: $O(m * n)$

Where $n$ is the number of visited urls, $m$ is the average length of each url, and $steps$ is the number of steps we go forward or back.