How do you approach Design Browser History?

Store visited pages in an array and keep a current index pointing at the page you are on.

What is the time complexity of Design Browser History?

Time complexity: O(1) amortized for visit, O(1) for back/forward.. Space complexity: O(n) for the stored history..

What are common mistakes on Design Browser History?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Design Browser History

MediumObject-Oriented Design

Description

Design a browser history. You start on the homepage, and you can visit new URLs, move back, and move forward.

visit(url) navigates to url from the current page and clears all forward history.
back(steps) moves back steps pages in history. If you can only move back fewer than steps pages, stop at the oldest page. Returns the current url after moving.
forward(steps) moves forward steps pages. If you can only move forward fewer than steps pages, stop at the newest page. Returns the current url after moving.

Implement the function browserHistory(homepage, operations) where homepage is the starting url and operations is a list of [op, ...args]: ["visit", url], ["back", steps], ["forward", steps]. For "visit" return null; for "back" and "forward" return the current url. Return the list of results, one per operation (use null for operations that return nothing).

Example 1

Input: homepage = "leetcode.com", operations = [["visit","google.com"],["visit","facebook.com"],["visit","youtube.com"],["back",1],["back",1],["forward",1],["visit","linkedin.com"],["forward",2],["back",2],["back",7]]

Output: [null, null, null, "facebook.com", "google.com", "facebook.com", null, "linkedin.com", "google.com", "leetcode.com"]

Example 2

Input: homepage = "a.com", operations = [["back",1],["forward",1],["visit","b.com"],["back",1]]

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

Example 3

Input: homepage = "home", operations = [["visit","p1"],["visit","p2"],["back",1],["visit","p3"],["forward",1]]

Output: [null, null, "p1", null, "p3"]

Constraints

1 <= url length <= 20. homepage and every url are valid strings. 1 <= steps <= 100. At most 5000 operations.

Design Browser History: approach, complexity and pitfalls

A medium design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Store visited pages in an array and keep a `current` index pointing at the page you are on.
On visit(url), truncate the array to everything up to and including `current` (this discards forward history), then append the new url and advance `current`.
back(steps) is current = max(0, current - steps); forward(steps) is current = min(length - 1, current + steps). Return the url at the new index.

The optimal approach

Show the approach: The approach

Model history as a list of urls plus a `current` index. The homepage seeds the list at index 0. `visit` discards any forward entries by truncating to `current + 1`, appends the new url, and advances `current`. `back` and `forward` clamp `current` to the `[0, length - 1]` range so you never run off either end, then return the url at the resulting index.

Time: O(1) amortized for visit, O(1) for back/forward.
Space: O(n) for the stored history.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.