Skip to main content
Talentd

Design Browser History - Solution & Explanation

MediumArrayLinked ListStackDesign20 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

  • BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
  • void visit(string url) Visits url from the current page. It clears up all the forward history.
  • string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
  • string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

 

Example:

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"]

Explanation:
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.

Approach Overview

Problem Overview: Design a browser history system that supports visiting new URLs and navigating backward or forward through previously visited pages. The structure must maintain order and correctly discard forward history when a new page is visited after moving back.

Approach 1: Using a List with Current Pointer (O(1) average per operation, O(n) space)

This approach stores all visited URLs in a dynamic array and maintains an index pointing to the current page. When you call visit(url), increment the pointer, overwrite any forward history, and append the new page if needed. The back(steps) operation moves the pointer left using max(0, current - steps), while forward(steps) moves it right but never past the last valid index. The key insight is that browser navigation behaves like moving a cursor in a sequence. This solution is easy to implement and relies only on an array and index arithmetic.

Approach 2: Using Two Stacks (O(1) per operation, O(n) space)

This method models browser navigation using two stacks: a back stack and a forward stack. The current page sits between them. When visiting a new page, push the current page onto the back stack and clear the forward stack because future pages are no longer reachable. For back(steps), repeatedly push the current page onto the forward stack and pop from the back stack. For forward(steps), do the reverse. This approach mirrors how many real browsers manage navigation history and directly uses the LIFO behavior of a stack. It is conceptually clean and common in system design interviews.

Both approaches represent the browsing sequence as a linear structure with a movable pointer. The list-based approach keeps everything in one container, while the stack-based solution explicitly separates backward and forward navigation states. The behavior is closely related to a doubly-linked list where each node has previous and next references.

Recommended for interviews: The list + pointer approach is usually the fastest to implement and keeps each operation constant time with minimal code. Interviewers also appreciate the two-stack design because it clearly models browser navigation logic. Demonstrating the list approach first shows you understand the state transitions, while presenting the stack approach highlights deeper understanding of stack-based navigation systems.

Approach 1: Approach Using a List

This approach involves using a list (or similar data structure) to keep track of the pages visited. We use an index to keep track of the current page. Visiting a new page from the current page will truncate the list beyond the current index before adding the new page. Moving back or forward adjusts the index within the bounds of the list.

In this implementation, the 'history' list keeps all the visited pages. 'current' is an integer that marks our current position in the history. When we visit a new URL, the function slices the list up to 'current' and appends the new URL, making sure to remove any forward history. The 'back' and 'forward' functions only adjust the current position and ensure it is within valid bounds.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing.
Space Complexity: O(n), where n is the number of URLs stored in history.

Try this approach in the editor →

Approach 2: Approach Using Two Stacks

This approach uses two stacks: one to store backward paths and another to store forward paths. The current page is not stored in the stack, but rather observed as the topmost element of the backward stack. The back function pops elements from the backward stack to the forward stack as necessary, and the forward function performs the opposite action. This effectively mimicks the process of moving through the history as we go back and forth.

In this Python solution, we use back_stack and forward_stack to keep track of visited pages. 'visit': Pushes the current page to back_stack and resets forward_stack. 'back': Pops pages from back_stack to forward_stack up to steps. 'forward': Pops pages from forward_stack back to back_stack up to steps.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks.
Space Complexity: O(n) for maintaining stacks with n pages.

Try this approach in the editor →

Approach 3: Two Stacks

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

When calling visit(url), we add url to stk1 and clear stk2. The time complexity is O(1).

When calling back(steps), we pop the top element from stk1 and push it to stk2. We repeat this operation steps times until the length of stk1 is 1 or steps is 0. Finally, we return the top element of stk1. The time complexity is O(steps).

When calling forward(steps), we pop the top element from stk2 and push it to stk1. We repeat this operation steps times until stk2 is empty or steps is 0. Finally, we return the top element of stk1. The time complexity is O(steps).

The space complexity is O(n), where n is the length of the browsing history.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach Using a List

Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing.
Space Complexity: O(n), where n is the number of URLs stored in history.

Approach Using Two Stacks

Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks.
Space Complexity: O(n) for maintaining stacks with n pages.

Two Stacks—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
List with Current PointerO(1) per operationO(n)Best for simple implementation using array and index tracking
Two StacksO(1) per operationO(n)When modeling browser navigation explicitly with back and forward stacks

Video Solution

Design Browser History - Leetcode 1472 - Python • NeetCodeIO • 31,575 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Browser History easy or hard?
Design Browser History is rated Medium difficulty. The operations themselves are simple, but the challenge is correctly handling forward history removal and navigation limits while keeping each operation O(1).
Design Browser History Python/Java solution
Python and Java solutions typically implement either a list with an index pointer or two stacks. Both versions maintain O(1) operations for visit, back, and forward while storing URLs in O(n) space. The logic remains identical across languages.
How to solve Design Browser History in O(1)?
Use either a dynamic array with a current index pointer or two stacks representing backward and forward history. Pointer movement or stack push/pop operations allow constant-time updates for each command. Both approaches maintain navigation state without scanning the entire history.
What is the best approach for Design Browser History?
The most common solution uses a list (array) with a pointer representing the current page. Visiting a new page overwrites forward history and moves the pointer forward, while back and forward operations simply adjust the pointer. Each operation runs in O(1) time with O(n) space for storing visited URLs.
Is Design Browser History asked at Google/Amazon/Meta?
Design-style data structure problems like browser history frequently appear in interviews at large tech companies including Amazon, Google, and Meta. The problem tests understanding of stacks, linked list behavior, and state transitions in system-like components.
What data structure is used in Design Browser History?
Common implementations use arrays, stacks, or a doubly linked list. Arrays with a pointer simulate cursor movement, while two stacks separate backward and forward navigation states. A doubly linked list is another natural representation because each page connects to previous and next nodes.
What is the time complexity of Design Browser History?
All core operations—visit, back, and forward—can be implemented in O(1) time. The data structure stores visited pages once, so total space complexity is O(n), where n is the number of visited URLs during the session.

Ready to solve this problem?

Practice Design Browser History with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Video Sharing Platform