#1472

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Design Browser History

Implement a browser history tracker with back, forward, and visit operations using linked-list pointer manipulation efficiently.

array linked list stack design doubly linked list

Problem Statement

Design a browser history manager that starts at a homepage and allows visiting new URLs, moving back a number of steps, or moving forward a number of steps. The class should track the current page and maintain the correct forward and backward history as operations are performed.

Implement the BrowserHistory class with the following methods: BrowserHistory(homepage) initializes the object with the homepage. visit(url) navigates to a new URL and clears forward history. back(steps) moves back in history up to the given number of steps. forward(steps) moves forward in history up to the given number of steps.

Examples

Example 1

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

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

BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com" browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com" browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com" browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com" browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com" browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com" browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com" browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps. browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com" browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Constraints

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.

Solution Approach

Use Doubly-Linked List

Create a doubly-linked list where each node represents a URL. Maintain a current pointer that moves back and forward by following prev and next pointers. Insert new nodes for each visit and cut off forward nodes if visiting after going back.

Use Two Stacks

Maintain one stack for back history and one for forward history. Push the current page to the back stack on visit, clear the forward stack, and move pages between stacks when performing back and forward operations.

Pointer Optimization

Optimize operations by keeping references instead of traversing the list. When visiting, directly attach a new node to the current node and nullify next pointers. For back and forward, move the current pointer while counting steps without extra memory overhead.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity for visit, back, and forward operations is O(1) per move if using a doubly-linked list with pointers, or O(steps) if using stacks. Space complexity is O(n) for storing up to n visited URLs, regardless of approach.

What Interviewers Usually Probe

You may be asked to justify linked-list vs stack trade-offs.
Clarify whether forward history should be cleared on new visits.
Expect questions about optimizing back and forward operations for large histories.

Common Pitfalls or Variants

Common pitfalls

Not clearing forward history after a new visit.
Using a singly-linked list which makes back operation inefficient.
Incorrectly updating current pointer when moving back or forward multiple steps.

Follow-up variants

Implement BrowserHistory with circular doubly-linked list for memory reuse.
Use array-based dynamic structure to simulate stacks for back and forward.
Extend to multi-tab browsing with separate histories per tab.

FAQ

What data structure is best for Design Browser History?

A doubly-linked list or two stacks are optimal, enabling efficient back, forward, and visit operations with pointer manipulation.

How do I handle forward history when visiting a new URL?

Clear all forward nodes or stack entries when a new URL is visited after moving back to ensure correct browser behavior.

Can I use an array instead of a linked list?

Yes, arrays can simulate stacks for back and forward operations, but moving multiple steps may require extra copying or pointer tracking.

Why is pointer manipulation crucial in this problem?

It allows moving back and forward efficiently without traversing the entire history, which is key for large sequences of operations.

What is the complexity of BrowserHistory operations?

Visit is O(1), back and forward are O(steps) if using stacks or O(1) per move using a doubly-linked list with pointers. Space is O(n) for storing URLs.

terminal

Solution

Solution 1: Two Stacks

We can use two stacks, $\textit{stk1}$ and $\textit{stk2}$, to store the back and forward pages, respectively. Initially, $\textit{stk1}$ contains the $\textit{homepage}$, and $\textit{stk2}$ is empty.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class BrowserHistory:
    def __init__(self, homepage: str):
        self.stk1 = []
        self.stk2 = []
        self.visit(homepage)

    def visit(self, url: str) -> None:
        self.stk1.append(url)
        self.stk2.clear()

    def back(self, steps: int) -> str:
        while steps and len(self.stk1) > 1:
            self.stk2.append(self.stk1.pop())
            steps -= 1
        return self.stk1[-1]

    def forward(self, steps: int) -> str:
        while steps and self.stk2:
            self.stk1.append(self.stk2.pop())
            steps -= 1
        return self.stk1[-1]


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

Continue Practicing

#1019 next greater node in linked list #706 design hashmap #705 design hashset