How do you solve Design Browser History on LeetCode?

Design Browser History (LeetCode #1472) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) for each operation time complexity and O(n) space complexity. Key insight: Using stacks allows for efficient back and forward navigation.

What is the brute force solution for Design Browser History?

The brute force approach for Design Browser History is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we can maintain a list of all visited URLs and use simple indexing to move back and forth in history. This is straightforward but inefficient for large histories. The optimal Optimal Solution approach improves this to O(1) for each operation.

What are the interview tips for Design Browser History?

Think about how you would implement a browser's back and forward buttons. Consider edge cases, such as trying to go back or forward when at the ends of history.

What are common mistakes when solving Design Browser History?

Not clearing the forward history when visiting a new URL. Incorrectly managing stack sizes during back and forward operations.

#1472

Design Browser History

Medium

ArrayLinked ListStackDesignDoubly-Linked ListData StreamStackArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1) for each operation
Space	O(1)	O(n)

💡

Intuition

Time O(1) for each operationSpace O(n)

Using two stacks allows us to efficiently manage the back and forward history without needing to copy lists. This approach is much faster and uses space effectively.

⚙️

Algorithm

4 steps

1Step 1: Initialize two stacks: one for back history and one for forward history.
2Step 2: For the 'visit' operation, push the current URL onto the back stack, clear the forward stack, and push the new URL onto the back stack.
3Step 3: For the 'back' operation, pop from the back stack and push to the forward stack, ensuring we do not exceed the stack size.
4Step 4: For the 'forward' operation, pop from the forward stack and push to the back stack, ensuring we do not exceed the stack size.

solution.py21 lines

1# Full working Python code
2class BrowserHistory:
3    def __init__(self, homepage: str):
4        self.back_stack = [homepage]
5        self.forward_stack = []
6
7    def visit(self, url: str) -> None:
8        self.back_stack.append(url)
9        self.forward_stack.clear()
10
11    def back(self, steps: int) -> str:
12        while steps > 0 and len(self.back_stack) > 1:
13            self.forward_stack.append(self.back_stack.pop())
14            steps -= 1
15        return self.back_stack[-1]
16
17    def forward(self, steps: int) -> str:
18        while steps > 0 and self.forward_stack:
19            self.back_stack.append(self.forward_stack.pop())
20            steps -= 1
21        return self.back_stack[-1]

ℹ

Complexity note: The time complexity is O(1) for each operation because we are only pushing and popping from stacks. The space complexity is O(n) due to the storage of history in stacks.

1Using stacks allows for efficient back and forward navigation.
2Clearing the forward history upon visiting a new URL is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.