MediumArrayLinked ListStackDesignDoubly-Linked List

Design Browser History

1 approach, code in every language

Model the history of a single browser tab that starts on a given homepage. As the user browses, you must support moving to new pages as well as stepping backward and forward through previously seen pages.

Implement the class BrowserHistory. The constructor receives the homepage string and opens the tab on that page. visit(url) navigates to url from the current page, which clears every page that was ahead in the forward history. back(steps) moves back at most steps pages, stopping at the oldest page if there are not enough, and returns the resulting url. forward(steps) moves forward at most steps pages, stopping at the newest page if there are not enough, and returns the resulting url.

Example 1

Input: operations = ["BrowserHistory", "visit", "visit", "visit", "back", "back", "forward", "visit", "forward", "back", "back"] args = [["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"]

After visiting three sites, back(1) lands on facebook.com and back(1) again on google.com. forward(1) returns to facebook.com. Visiting linkedin.com erases the forward pages, so forward(2) cannot advance and stays on linkedin.com; back(2) reaches google.com and back(7) clamps to leetcode.com.

Example 2

Input: operations = ["BrowserHistory", "back", "forward", "visit"] args = [["a.com"], [3], [2], ["b.com"]]

Output: [null, "a.com", "a.com", null]

With only the homepage present, back and forward both clamp to a.com. Visiting b.com then moves the current page forward to b.com.

Constraints

1 <= homepage.length <= 20 and 1 <= url.length <= 20
1 <= steps <= 100
At most 5 * 10^4 total calls will be made to visit, back, and forward.

Dynamic Array with a Current Pointer

Store visited urls in a growable list and track the current index; visiting truncates the forward tail, while back and forward clamp the index.

Loading animation…

Intuition

Browsing is a straight line of pages with a cursor pointing at the page you are on. Everything before the cursor is your back history and everything after it is your forward history. When you visit a new page, any forward pages become unreachable, so we discard them and append the new page right after the cursor. Moving back or forward is just shifting the cursor, clamped so it never leaves the valid range of pages. Because the pages are stored in a contiguous array, every operation is a simple index update and lookup.

Algorithm walkthrough

1Initialize the history list with the homepage and set the current index to 0.
2For visit(url), drop every entry after the current index, append url, and advance the current index to point at it.
3For back(steps), subtract steps from the current index but never go below 0, then return the url at that index.
4For forward(steps), add steps to the current index but never exceed the last valid index, then return the url at that index.
5Truncating on visit is what enforces the rule that navigating to a new page erases the forward history.
6Each operation touches only the index and, at most, trims or appends to the tail, so it is effectively constant time per navigation.

Implementation

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

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

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

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

Time

O(1) amortized for visit, back, and forward, aside from the occasional tail truncation on visit.

Space

O(n) where n is the number of pages currently stored in the history.

A doubly linked list gives the same behavior; the array keeps the pointer math simple and cache friendly.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free