Domain 2MediumMEDIUM

Design Browser History

Simulate browser navigation using a list to store history and an index pointer. Truncate the list on visit to clear forward path.

Domain: medium•Updated: 2026-09-17
#array#pointer manipulation#O(1)#amortized O(N)

Problem Breakdown

We need to implement a BrowserHistory class that maintains a sequence of visited URLs (history) and allows navigation between them. The state consists of two parts: the list of all valid history pages currently in memory, and an integer pointer indicating the current page’s position within that list.

Inputs:

  • homepage: Initial URL string.
  • url, steps: Strings for new URLs to visit, integers representing navigation steps (back/forward).

Outputs:

  • Current page URL (string) after moving back or forward.
  • Void (None) when visiting a new URL.

Implicit Constraints & Edge Cases:

  1. Forward History Clearing: Visiting a new URL invalidates any future navigation from the current point (forward history). We must discard URLs that were previously “ahead” of our position before visiting again.
  2. Bounds Checking: Moving steps back or forward might exceed available history depth (e.g., trying to go back more than pages visited, or going past the end). The logic must clamp movement to valid indices without throwing errors.
  3. State Management: We need a way to track the current index and access URLs efficiently in both directions.

Intuition

A naive approach would be to store all history but managing pointers inefficiently could lead to O(N) operations per move if not careful with memory management.

However, since we need random access (jumping back/forward), a simple list/array is sufficient because Python lists support efficient indexing and slicing. The key insight is that visit acts as a “reset” for the forward path relative to our current position. We can maintain a single history array where:

  • Back: Decrement an index pointer, ensuring we don’t go below 0.
  • Forward: Increment an index pointer, ensuring we don’t exceed list length - 1.
  • Visit: Truncate the list to keep only up-to-current-index elements (clearing forward history), then append the new URL and update current position.

This avoids complex data structures like Doubly Linked Lists while satisfying O(1) access for navigation, with Visit being proportional to cleared nodes which is acceptable given constraints (N≤5000N \le 5000). In Python, list slicing overhead is often lower than creating custom node objects due to interpreter optimizations and memory locality.

Approach

  1. Initialization: Create a list history containing the homepage and an integer pointer _index set to 0 (pointing at homepage).
  2. Visit Method:
    • Truncate history so it only contains elements up to _index. This effectively discards all forward history from previous visits that are no longer reachable or valid after this new visit.
    • Append the new URL.
    • Update _index to point at the newly added URL (which is now the last element).
  3. Back Method:
    • Calculate how many steps we can actually move back: min(steps, _index).
    • Subtract this from _index.
    • Return history[_index].
  4. Forward Method:
    • Calculate available forward space: (len(history) - 1) - _index.
    • Move steps by taking the minimum of requested steps and available space.
    • Add to _index and return URL at new index.

Complexity Analysis

  • Time Complexity:
    • visit: O(K), where K is the number of forward URLs cleared (worst case N). Given constraints, this fits within time limits easily. Amortized cost over many operations remains low because we only store valid history and memory allocation handles garbage collection efficiently in Python.
    • back / forward: O(1) as they involve simple arithmetic and list indexing.
  • Space Complexity: O(N), where N is the number of unique URLs stored in our active history buffer at any given time (bounded by total calls).

Solution

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.current_index = 0
    
    def visit(self, url: str) -> None:
        # Visit clears forward history. 
        # We truncate the list to keep only up-to-current page and append new URL.
        self.history = self.history[:self.current_index + 1]
        self.history.append(url)
        self.current_index += 1
    
    def back(self, steps: int) -> str:
        # Move back as many steps as possible without going below index 0
        move_back = min(steps, self.current_index)
        self.current_index -= move_back
        return self.history[self.current_index]
    
    def forward(self, steps: int) -> str:
        # Calculate available space to move forward
        max_forward = len(self.history) - 1 - self.current_index
        move_forward = min(steps, max_forward)
        self.current_index += move_forward
        return self.history[self.current_index]