1472. Design Browser History - Detailed Explanation

Problem Statement

You need to implement a browser history manager supporting three operations on strings representing URLs:

• visit(url): navigate to url from the current page. This clears any “forward” history.
• back(steps): move back up to steps pages; return the current page after moving.
• forward(steps): move forward up to steps pages; return the current page.

Examples

Example 1

Input:
  BrowserHistory bh = new BrowserHistory("leetcode.com");
  bh.visit("google.com");
  bh.visit("facebook.com");
  bh.visit("youtube.com");
  bh.back(1);    // returns "facebook.com"
  bh.back(1);    // returns "google.com"
  bh.forward(1); // returns "facebook.com"
  bh.visit("linkedin.com");
  bh.forward(2); // returns "linkedin.com"  (no forward history)
  bh.back(2);    // returns "google.com"
  bh.back(7);    // returns "leetcode.com"

Explanation

• Start at “leetcode.com”
• Visits build history: [leetcode→google→facebook→youtube], current=“youtube”
• back(1) → “facebook”
• back(1) → “google”
• forward(1) → “facebook”
• visit("linkedin.com") wipes forward to yield [leetcode→google→facebook→linkedin], current=“linkedin”
• forward(2) can’t go forward → stays “linkedin”
• back(2) → “google”
• back(7) → hits oldest “leetcode”

Example 2

Input:
  BrowserHistory bh = new BrowserHistory("a.com");
  bh.visit("b.com");
  bh.back(1);    // "a.com"
  bh.visit("c.com");
  bh.forward(1); // "c.com"

Constraints

• All URLs are non‑empty strings of length ≤ 20, consisting of letters, digits, ‘.’ and ‘/’.
• Total calls ≤ 5 × 10⁴.
• 1 ≤ steps ≤ 100.

Hints

1. How would you implement this with an array/list and a current‑index pointer?
2. How do you “clear forward history” when visiting a new URL?
3. Can two stacks (back and forward) give O(1) for each operation?
4. Could a doubly linked list with a current pointer work too?

Approach 1 – ArrayList + Current Index

Idea

Keep a resizable array history[] and an integer curIdx.

• visit(url): truncate history to length curIdx+1, append url, set curIdx = end.
• back(steps): curIdx = max(0, curIdx - steps); return history[curIdx].
• forward(steps): curIdx = min(history.size()-1, curIdx + steps); return history[curIdx].

Walkthrough

Using Example 1:

1. init: history=["leetcode.com"], curIdx=0
2. visit “google.com”: truncate to [0], append → ["leetcode","google"], curIdx=1
3. visit “facebook.com”: → ["leetcode","google","facebook"], curIdx=2
4. visit “youtube.com”: → ["leetcode","google","facebook","youtube"], curIdx=3
5. back(1): curIdx=2, return "facebook"
6. back(1): curIdx=1, return "google"
7. forward(1): curIdx=2, return "facebook"
8. visit “linkedin.com”: truncate to idx=2 → keep ["leetcode","google","facebook"], append → ["leetcode","google","facebook","linkedin"], curIdx=3
9. forward(2): curIdx = min(3,3+2)=3, return "linkedin"
10. back(2): curIdx=1, return "google"
11. back(7): curIdx=0, return "leetcode"

Complexity

• Time: All ops O(1) amortized for index math and list append/truncate.
• Space: O(N) for history, N ≤ number of visits.

Python Code