628/670

628. Design Browser History

Medium

Model the back/forward navigation of a single browser tab. Implement a class BrowserHistory:

BrowserHistory(homepage) — the tab starts out on homepage.
visit(url) — navigate from the current page to url. Everything that was reachable with the forward button is discarded.
back(steps) — move backward through history up to steps pages (fewer if the oldest page is reached first) and return the url you land on.
forward(steps) — move forward up to steps pages (fewer if the newest reachable page is reached first) and return the url you land on.

The judge constructs one BrowserHistory and drives it with a sequence of operations; the output is whatever your back and forward calls return, in order.

Example 1:

Input: BrowserHistory("wiki.org") · visit("news.com") · visit("maps.io") · back(1) · back(5) · forward(1) · visit("mail.dev") · forward(3)

Output: "news.com", "wiki.org", "news.com", "mail.dev"

Explanation: History grows to [wiki.org, news.com, maps.io]. back(1) lands on news.com; back(5) can only rewind one more page, so it stops at wiki.org. forward(1) returns to news.com. visit(mail.dev) erases maps.io from the forward side, so forward(3) has nowhere to go and stays on mail.dev.

Example 2:

Input: BrowserHistory("a.com") · visit("b.com") · back(1) · forward(1)

Output: "a.com", "b.com"

Explanation: After visiting b.com, back(1) returns to the homepage and forward(1) re-enters b.com.

Constraints:

1 ≤ homepage.length, url.length ≤ 20
urls consist of lowercase letters, digits, and '.'
1 ≤ steps ≤ 100
At most 5000 total calls to visit, back, and forward.

Hints:

History is a timeline of pages and you are standing somewhere on it. What single piece of state tells you where you stand?

Keep the pages in an array with two indices: `cur` (the page on screen) and `last` (the newest page still reachable by forward). Then back/forward are just clamped index arithmetic, and visit writes at `cur + 1` and pulls `last` back.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: BrowserHistory("wiki.org") · visit("news.com") · visit("maps.io") · back(1) · back(5) · forward(1) · visit("mail.dev") · forward(3)

Expected output: "news.com", "wiki.org", "news.com", "mail.dev"