How do you solve Design Browser History?

Maintain three variables: back_stack, forward_stack, and curr (current page). On visit, push curr to back_stack, update curr, and clear forward_stack. On back, pop from back_stack to curr and push previous curr to forward_stack up to steps times or until back_stack is empty. On forward, pop from forward_stack to curr and push previous curr to back_stack similarly. Return curr after back and forward operations.

What pattern does Design Browser History use?

The Pattern: Simulation (Stateful Stack-Based History Management) The Heuristic: Model bidirectional navigation by maintaining two stacks representing backward and forward history, pushing and popping pages to simulate user navigation efficiently and cleanly.

Design Browser History — Simulation

Q: What is the time complexity of Design Browser History?

O(steps) per back or forward call, O(1) per visit call. Each back or forward operation moves pages between stacks up to the number of steps requested, resulting in O(steps) time. Visit operations perform constant-time stack operations.

Problem

Implement a browser history system that supports visiting new URLs, moving back in history by a given number of steps, and moving forward in history by a given number of steps, returning the current URL after each operation.

1 ≤ steps ≤ 100
1 ≤ url.length ≤ 20
url consists of lowercase English letters and '.'
At most 5000 calls will be made to visit, back, and forward.

Example

Input:

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");
browserHistory.visit("facebook.com");
browserHistory.visit("youtube.com");
browserHistory.back(1);
browserHistory.back(1);
browserHistory.forward(1);
browserHistory.visit("linkedin.com");
browserHistory.forward(2);
browserHistory.back(2);
browserHistory.back(7);

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

Start at 'leetcode.com'. Visit 'google.com', 'facebook.com', and 'youtube.com' sequentially, building back history. Back(1) moves from 'youtube.com' to 'facebook.com'. Back(1) moves to 'google.com'. Forward(1) moves to 'facebook.com'. Visit('linkedin.com') clears forward history and sets current to 'linkedin.com'. Forward(2) has no effect since forward history is empty. Back(2) moves back to 'google.com'. Back(7) moves back as far as possible to 'leetcode.com'.

Approach

Straightforward Solution

One could store the entire history in a list and maintain an index pointer for the current page. Moving back or forward would adjust the index accordingly. However, clearing forward history on visit requires slicing or resetting the list, which can be inefficient.

Core Observation

Browser navigation can be modeled as a linear history with a current position, where moving back and forward corresponds to moving along this history. Using two stacks to represent backward and forward history allows efficient simulation of these movements.

Path to Optimal

Preview

Using two stacks cleanly separates backward and forward history. The back stack holds pages visited before the current one, and the forward stack holds pages ahead…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Maintain three variables: back_stack, forward_stack, and curr (current page). On visit, push curr to back_stack, update curr, and clear forward_stack…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(steps) per back or forward call, O(1) per visit call

Each back or forward operation moves pages between stacks up to the number of steps requested, resulting in O(steps) time. Visit operations perform constant-time stack operations.

Space

O(n)

The space used is proportional to the number of visited pages stored in the back and forward stacks, which can grow linearly with the number of visit calls.

Solution

Python

1class BrowserHistory:
2
  def __init__(self, homepage: str):
      self.back_stack = []
      self.forward_stack = []
      self.curr = homepage
7
  def visit(self, url: str) -> None:
      self.back_stack.append(self.curr)
      self.curr = url
      self.forward_stack = []
12
  def back(self, steps: int) -> str:
      while steps > 0 and self.back_stack:
          self.forward_stack.append(self.curr)
          self.curr = self.back_stack.pop()
          steps -= 1
      return self.curr
19
  def forward(self, steps: int) -> str:
      while steps > 0 and self.forward_stack:
          self.back_stack.append(self.curr)
          self.curr = self.forward_stack.pop()
          steps -= 1
      return self.curr

Step-by-Step Solution

1

Initialize Browser History State with Homepage

4self.back_stack = []
5self.forward_stack = []
6self.curr = homepage

Objective

To set up the initial browser state with empty back and forward stacks and the current page set to the homepage.

Key Insight

Starting with empty stacks ensures no backward or forward history exists initially. Setting the current page to the homepage reflects the browser's starting point. This clean separation of state variables simplifies subsequent navigation operations.

Interview Quick-Check

Core Logic

The back and forward stacks represent navigation history before and after the current page, respectively.

State & Boundaries

The current page is stored separately to allow O(1) access and updates during navigation.

2

Visit a New URL and Reset Forward History

To record the current page in back history, update the current page to the new URL, and clear forward history.

3

Move Backward in History Up to Steps

To move back in history by popping pages from the back stack to the current page and pushing the previous current page onto the forward stack, up to the requested number of steps.

4

Move Forward in History Up to Steps

To move forward in history by popping pages from the forward stack to the current page and pushing the previous current page onto the back stack, up to the requested number of steps.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 9 Critical

self.back_stack.append(self.curr)

Push the current page onto the back stack before visiting a new URL.

Preserving the current page in back history allows the user to return to it after visiting a new page, maintaining correct navigation order.

Line 11 Critical

self.forward_stack = []

Clear the forward stack to discard forward history after visiting a new page.

Visiting a new page invalidates any forward history, so clearing the forward stack prevents incorrect forward navigation.

Line 16 Critical

self.curr = self.back_stack.pop()

Pop the most recent page from the back stack and set it as the current page.

This updates the current page to the previous page in history, simulating the back button behavior.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does using two stacks to represent backward and forward history correctly simulate browser navigation?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Design Browser History from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Design Browser History drill

or drill a free problem

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