Problem Description

You need to implement a browser history system that simulates the back and forward navigation functionality of a web browser with a single tab.

The browser starts on a homepage, and you can:

• Visit new URLs (which clears any forward history)
• Navigate backward through your browsing history
• Navigate forward through pages you've gone back from

The BrowserHistory class requires implementing four methods:

1. Constructor BrowserHistory(string homepage): Initializes the browser with a starting homepage.

2. Visit visit(string url): Navigate to a new URL from the current page. This action clears all forward history (any pages you could have gone forward to are lost).

3. Back back(int steps): Move backward in history by up to steps pages. If there are fewer than steps pages in the backward history, move back as far as possible. Returns the URL of the page you land on.

4. Forward forward(int steps): Move forward in history by up to steps pages. If there are fewer than steps pages in the forward history, move forward as far as possible. Returns the URL of the page you land on.

The solution uses two stacks to track navigation:

• stk1: Stores the current page and all pages in the backward history
• stk2: Stores pages that can be reached by going forward (pages you've gone back from)

When visiting a new URL, it's added to stk1 and stk2 is cleared (forward history is lost). When going back, pages are moved from stk1 to stk2. When going forward, pages are moved from stk2 back to stk1. The current page is always at the top of stk1.

Intuition

Think about how a real browser's back and forward buttons work. When you visit pages A → B → C, then press back twice to return to A, you create a situation where B and C are "ahead" of you - accessible via the forward button. But if you visit a new page D while at A, those forward pages (B and C) disappear forever.

This behavior naturally suggests using two separate data structures: one for pages "behind" us (where back takes us) and one for pages "ahead" of us (where forward takes us).

Why stacks? Consider the order of access:

• When going back, we access the most recently visited page first (LIFO - Last In, First Out)
• When going forward, we revisit pages in the reverse order of how we backed away from them (also LIFO)

The key insight is that the current page should always be part of the "back history" since we need to return to it if we navigate away. So we maintain:

• stk1: Contains the current page at the top, with all previous pages below it
• stk2: Contains pages we can go forward to (pages we've backed away from)

When we go back, we're essentially "undoing" our browsing - we pop from stk1 (removing the current page from back history) and push it to stk2 (making it available for forward navigation). The opposite happens when going forward.

The visiting action is straightforward: add the new URL to our back history (stk1) and clear the forward history (stk2) since those pages are no longer reachable - just like in a real browser where visiting a new page eliminates the forward button's history.

Learn more about Stack, Linked List and Data Stream patterns.

Solution Approach

The implementation uses two stacks to manage browser history navigation:

Data Structures:

• stk1: Stores the current page and all pages in the backward history
• stk2: Stores pages available for forward navigation

Implementation Details:

1. Initialization (__init__):

   • Create two empty stacks: stk1 and stk2
   • Call visit(homepage) to add the homepage to stk1
   • This ensures the browser starts with the homepage as the current page

2. Visit a new URL (visit):

   • Append the new url to stk1 (making it the current page)
   • Clear stk2 entirely using stk2.clear()
   • This reflects the browser behavior where visiting a new page eliminates all forward history
   • Time complexity: O(1)

3. Navigate backward (back):

   • Use a while loop with two conditions:
     • steps > 0: Still have steps to go back
     • len(stk1) > 1: Keep at least one page in stk1 (can't go back from the first page)
   • In each iteration:
     • Pop the top element from stk1 and push it to stk2
     • Decrement steps by 1
   • Return stk1[-1] (the new current page at the top of stk1)
   • Time complexity: O(steps)

4. Navigate forward (forward):

   • Use a while loop with two conditions:
     • steps > 0: Still have steps to go forward
     • stk2 is not empty: There are pages to go forward to
   • In each iteration:
     • Pop the top element from stk2 and push it to stk1
     • Decrement steps by 1
   • Return stk1[-1] (the new current page at the top of stk1)
   • Time complexity: O(steps)

The elegance of this solution lies in how the two stacks naturally maintain the relationship between back and forward histories. The current page is always stk1[-1], and the movement between stacks during back/forward operations preserves the correct ordering of pages.

Example Walkthrough

Let's walk through a sequence of browser operations to see how the two-stack solution works:

Initial State: Start with homepage "google.com"

• After BrowserHistory("google.com"):
  • stk1 = ["google.com"] (current page at top)
  • stk2 = [] (no forward history)

Step 1: Visit "leetcode.com"

• After visit("leetcode.com"):
  • stk1 = ["google.com", "leetcode.com"]
  • stk2 = [] (cleared on visit)

Step 2: Visit "facebook.com"

• After visit("facebook.com"):
  • stk1 = ["google.com", "leetcode.com", "facebook.com"]
  • stk2 = []

Step 3: Visit "youtube.com"

• After visit("youtube.com"):
  • stk1 = ["google.com", "leetcode.com", "facebook.com", "youtube.com"]
  • stk2 = []

Step 4: Go back 1 step

• During back(1):
  • Pop "youtube.com" from stk1, push to stk2
  • stk1 = ["google.com", "leetcode.com", "facebook.com"]
  • stk2 = ["youtube.com"]
  • Returns: "facebook.com" (top of stk1)

Step 5: Go back 1 more step

• During back(1):
  • Pop "facebook.com" from stk1, push to stk2
  • stk1 = ["google.com", "leetcode.com"]
  • stk2 = ["youtube.com", "facebook.com"]
  • Returns: "leetcode.com"

Step 6: Go forward 1 step

• During forward(1):
  • Pop "facebook.com" from stk2, push to stk1
  • stk1 = ["google.com", "leetcode.com", "facebook.com"]
  • stk2 = ["youtube.com"]
  • Returns: "facebook.com"

Step 7: Visit "linkedin.com" (demonstrates clearing forward history)

• After visit("linkedin.com"):
  • stk1 = ["google.com", "leetcode.com", "facebook.com", "linkedin.com"]
  • stk2 = [] (cleared! "youtube.com" is lost forever)

Step 8: Try to go back 5 steps (more than available)

• During back(5):
  • Can only go back 3 steps (keeping at least 1 page in stk1)
  • Move "linkedin.com", "facebook.com", "leetcode.com" to stk2
  • stk1 = ["google.com"]
  • stk2 = ["linkedin.com", "facebook.com", "leetcode.com"]
  • Returns: "google.com"

This example demonstrates all key behaviors:

• The current page is always at the top of stk1
• Going back moves pages from stk1 to stk2 in reverse order
• Going forward moves pages from stk2 back to stk1
• Visiting a new URL clears all forward history in stk2
• We maintain at least one page in stk1 when going back

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(homepage): O(1) - Simply initializes two empty stacks and calls visit once
• visit(url): O(1) - Appends to stk1 and clears stk2, both constant time operations
• back(steps): O(min(steps, len(stk1) - 1)) - In the worst case, moves steps elements from stk1 to stk2, but limited by the available history
• forward(steps): O(min(steps, len(stk2))) - In the worst case, moves steps elements from stk2 to stk1, but limited by the forward history

Space Complexity: O(n), where n is the total number of URLs in the browsing history. The two stacks stk1 and stk2 together store all visited URLs. At any point in time, the total number of elements across both stacks equals the number of unique visits made (after considering that visiting a new URL clears the forward history). The maximum space used is proportional to the total number of URLs visited.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Clear Forward History on Visit

One of the most common mistakes is forgetting to clear the forward stack when visiting a new URL. This violates the expected browser behavior where visiting a new page eliminates all forward history.

Incorrect Implementation:

def visit(self, url: str) -> None:
    self.history_stack.append(url)
    # Missing: self.forward_stack.clear()

Why it's wrong: If you navigate back a few pages and then visit a new URL, you should not be able to forward to the pages you previously backed out from. The forward history must be cleared.

Correct Implementation:

def visit(self, url: str) -> None:
    self.history_stack.append(url)
    self.forward_stack.clear()  # Essential to clear forward history

2. Going Back Too Far (Empty Stack Issue)

Another critical mistake is allowing the history stack to become empty when going back, which would cause an index error when trying to return the current page.

Incorrect Implementation:

def back(self, steps: int) -> str:
    while steps > 0 and self.history_stack:  # Wrong condition!
        self.forward_stack.append(self.history_stack.pop())
        steps -= 1
    return self.history_stack[-1]  # This will fail if stack is empty!

Why it's wrong: The condition self.history_stack allows the stack to become completely empty. When we try to access self.history_stack[-1], it will raise an IndexError.

Correct Implementation:

def back(self, steps: int) -> str:
    while steps > 0 and len(self.history_stack) > 1:  # Keep at least 1 page
        self.forward_stack.append(self.history_stack.pop())
        steps -= 1
    return self.history_stack[-1]  # Safe - always has at least one element

3. Incorrect Stack Order During Navigation

Some implementations mistakenly push elements in the wrong order or to the wrong stack during back/forward operations.

Incorrect Implementation:

def back(self, steps: int) -> str:
    while steps > 0 and len(self.history_stack) > 1:
        # Wrong: pushing to beginning instead of end
        self.forward_stack.insert(0, self.history_stack.pop())
        steps -= 1
    return self.history_stack[-1]

Why it's wrong: Using insert(0, ...) changes the order of elements in the forward stack, breaking the LIFO (Last In, First Out) property required for correct navigation.

Correct Implementation:

def back(self, steps: int) -> str:
    while steps > 0 and len(self.history_stack) > 1:
        self.forward_stack.append(self.history_stack.pop())  # Maintain LIFO order
        steps -= 1
    return self.history_stack[-1]

4. Not Initializing Homepage Properly

Some forget to actually visit the homepage in the constructor, leaving the browser in an invalid state.

Incorrect Implementation:

def __init__(self, homepage: str):
    self.history_stack = [homepage]  # Direct assignment
    self.forward_stack = []

Why it's problematic: While this might seem to work, it bypasses the visit method's logic. If visit is later modified to include additional functionality (like logging or validation), the homepage won't benefit from these changes.

Correct Implementation:

def __init__(self, homepage: str):
    self.history_stack = []
    self.forward_stack = []
    self.visit(homepage)  # Use the visit method for consistency

5. Off-by-One Errors in Step Counting

Be careful with the loop conditions and step counting to avoid navigating one page too many or too few.

Incorrect Implementation:

def back(self, steps: int) -> str:
    while steps >= 0 and len(self.history_stack) > 1:  # >= is wrong!
        self.forward_stack.append(self.history_stack.pop())
        steps -= 1
    return self.history_stack[-1]

Why it's wrong: Using steps >= 0 will execute one extra iteration when steps reaches 0, moving back one page more than requested.

Correct Implementation:

def back(self, steps: int) -> str:
    while steps > 0 and len(self.history_stack) > 1:  # Correct: steps > 0
        self.forward_stack.append(self.history_stack.pop())
        steps -= 1
    return self.history_stack[-1]