1472. Design Browser History

Problem¶

Implement a one-tab browser history. Visiting a URL discards all forward history; moving back or forward stops at the available boundary.

Start: a.com
visit(b.com), visit(c.com), back(1) -> b.com
visit(d.com), forward(1) -> d.com  # c.com was discarded

class BrowserHistory:
    def __init__(self, homepage: str):
        pass

    def visit(self, url: str) -> None:
        pass

    def back(self, steps: int) -> str:
        pass

    def forward(self, steps: int) -> str:
        pass

Key trick¶

Keep the URLs in a list and the current position as an index. On a visit, delete everything after that index before appending the new URL.

Trap¶

Moving back does not delete forward history. Only a new visit does.

Why is it interesting?¶

The current page is not necessarily the last item in the list, so navigation and branching require different updates.

Python solution¶

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

    def visit(self, url: str) -> None:
        # A new visit replaces the entire forward branch.
        del 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]

Time: \(O(n)\) for visit when deleting forward history; \(O(1)\) for back and forward.
Space: \(O(n)\) for \(n\) retained URLs.

Comment on my solution¶

Your solution is correct. The second [:] in self.history[:self.pos + 1][:] makes an unnecessary copy. Replacing that assignment with del self.history[self.pos + 1:] removes the forward history in place.

class BrowserHistory:

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


    def visit(self, url: str) -> None:
        self.history = self.history[:self.pos + 1][:]
        self.history.append(url)
        self.pos = len(self.history) - 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]