Skip to main content
CodeEasy v0.1

Design Browser History

Medium Subject: Design
Time Complexity
O(1) except visit which is O(K) due to truncation
Space Complexity
O(N)

Problem Description

Problem Statement

You have a browser of one tab where you start on the homepage. You can visit a URL, or move back or forward in history. Implement the BrowserHistory class with visit(url), back(steps), and forward(steps).

Example 1:

  • Input: ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]\n[["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"]

Optimal Solution

Python

Approach: Array / List with Pointer

We can use an array to store the history of visited URLs and an integer pointer curr to track our current position. When we visit a new URL, we truncate all URLs after curr, append the new URL, and increment curr. For back and forward, we simply move the pointer within bounds.

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

    def visit(self, url: str) -> None:
        # Truncate 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]