Design Browser History solution and explanation
Google
9 more videos on this problem
Design Browser History - Leetcode 1472 - PythonNeetCodeIO · 13:30 · 31K views
Design Browser History | Java | LeetCode - Medium - 1472 | The Code MateThe Code Mate · 18:08 · 5K views
[Java] Leetcode 1472. Design Browser History [Design #3]Eric Programming · 13:32 · 2K views
Design Browser History - Leetcode 1472 - PythonTechError · 7:10 · 825 views
1472. Design Browser History - JAVA (Doubly Linked List - Detailed explanation)Sourin Majumdar · 10:37 · 587 views
Leetcode Solution - 1472 Design Browser HistoryJohn Leonardo · 5:28 · 553 views
LeetCode 1472 Design Browser History | JSer - JavaScript & AlgorithmJSer · 7:23 · 438 views
LeetCode 1472 - Design Browser History - Python SolutionCode with Carter · 11:38 · 394 views
LeetCode 1472. Design Browser HistoryGarrett Smith · 9:52 · 300 views
Leetcode 1472 Design Browser History - Frequently Asked Question - FacebookAlgorithmicIQ · 25:49 · 294 views
The problem
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 thehomepageof the browser.void visit(string url)Visitsurlfrom the current page. It clears up all the forward history.string back(int steps)Movestepsback in history. If you can only returnxsteps in the history andsteps > x, you will return onlyxsteps. Return the currenturlafter moving back in history at moststeps.string forward(int steps)Movestepsforward in history. If you can only forwardxsteps in the history andsteps > x, you will forward onlyxsteps. Return the currenturlafter forwarding in history at moststeps.
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 <= 201 <= url.length <= 201 <= steps <= 100homepageandurlconsist of '.' or lower case English letters.- At most
5000calls will be made tovisit,back, andforward.
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.
class BrowserHistory:
def __init__(self, homepage: str):
self.history = [homepage] # List to maintain the browsing history
self.current = 0 # Current index in history
def visit(self, url: str) -> None:
# Discard forward history and append new entry
self.history = self.history[:self.current+1]
self.history.append(url)
self.current += 1
def back(self, steps: int) -> str:
# Move back, ensuring we do not go past the first page
self.current = max(0, self.current - steps)
return self.history[self.current]
def forward(self, steps: int) -> str:
# Move forward, ensuring we do not go beyond the last visited page
self.current = min(len(self.history) - 1, self.current + steps)
return self.history[self.current]import java.util.ArrayList;
class BrowserHistory {
private ArrayList<String> history;
private int current;
public BrowserHistory(String homepage) {
history = new ArrayList<>();
history.add(homepage);
current = 0;
}
public void visit(String url) {
while(history.size() > current + 1) history.remove(history.size() - 1);
history.add(url);
current++;
}
public String back(int steps) {
current = Math.max(0, current - steps);
return history.get(current);
}
public String forward(int steps) {
current = Math.min(history.size() - 1, current + steps);
return history.get(current);
}
}#include <vector>
#include <string>
class BrowserHistory {
std::vector<std::string> history;
int current;
public:
BrowserHistory(std::string homepage) {
history.push_back(homepage);
current = 0;
}
void visit(std::string url) {
history.resize(current + 1);
history.push_back(url);
current++;
}
std::string back(int steps) {
current = std::max(0, current - steps);
return history[current];
}
std::string forward(int steps) {
current = std::min((int)history.size() - 1, current + steps);
return history[current];
}
};class BrowserHistory {
constructor(homepage) {
this.history = [homepage];
this.current = 0;
}
visit(url) {
this.history = this.history.slice(0, this.current + 1);
this.history.push(url);
this.current++;
}
back(steps) {
this.current = Math.max(0, this.current - steps);
return this.history[this.current];
}
forward(steps) {
this.current = Math.min(this.history.length - 1, this.current + steps);
return this.history[this.current];
}
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct {
char **history;
int size;
int current;
int capacity;
} BrowserHistory;
BrowserHistory* browserHistoryCreate(char *homepage) {
BrowserHistory *obj = (BrowserHistory *)malloc(sizeof(BrowserHistory));
obj->history = (char **)malloc(5000 * sizeof(char*));
obj->history[0] = strdup(homepage);
obj->capacity = 5000;
obj->size = 1;
obj->current = 0;
return obj;
}
void browserHistoryVisit(BrowserHistory* obj, char *url) {
while (obj->size > obj->current + 1) {
free(obj->history[--obj->size]);
}
obj->history[obj->size++] = strdup(url);
obj->current = obj->size - 1;
}
char *browserHistoryBack(BrowserHistory* obj, int steps) {
obj->current = (steps > obj->current) ? 0 : obj->current - steps;
return obj->history[obj->current];
}
char *browserHistoryForward(BrowserHistory* obj, int steps) {
obj->current = (steps + obj->current >= obj->size) ? obj->size - 1 : obj->current + steps;
return obj->history[obj->current];
}
void browserHistoryFree(BrowserHistory* obj) {
for (int i = 0; i < obj->size; i++) {
free(obj->history[i]);
}
free(obj->history);
free(obj);
}using System;
using System.Collections.Generic;
public class BrowserHistory {
private List<string> history;
private int current;
public BrowserHistory(string homepage) {
history = new List<string>() { homepage };
current = 0;
}
public void Visit(string url) {
history = history.GetRange(0, current + 1);
history.Add(url);
current++;
}
public string Back(int steps) {
current = Math.Max(0, current - steps);
return history[current];
}
public string Forward(int steps) {
current = Math.Min(history.Count - 1, current + steps);
return history[current];
}
}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.
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 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.
class BrowserHistory:
def __init__(self, homepage: str):
self.back_stack = [] # Stack to keep history for 'back' functionality
self.forward_stack = [] # Stack to keep history for 'forward' functionality
self.current = homepage
def visit(self, url: str) -> None:
# Visiting clears forward history
self.back_stack.append(self.current)
self.current = url
self.forward_stack = []
def back(self, steps: int) -> str:
# Move elements from back stack to forward stack
for _ in range(min(steps, len(self.back_stack))):
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self, steps: int) -> str:
# Move elements from forward stack back to the current
for _ in range(min(steps, len(self.forward_stack))):
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.currentimport java.util.Stack;
class BrowserHistory {
private Stack<String> backStack;
private Stack<String> forwardStack;
private String current;
public BrowserHistory(String homepage) {
backStack = new Stack<>();
forwardStack = new Stack<>();
current = homepage;
}
public void visit(String url) {
backStack.push(current);
current = url;
forwardStack.clear();
}
public String back(int steps) {
while (steps > 0 && !backStack.isEmpty()) {
forwardStack.push(current);
current = backStack.pop();
steps--;
}
return current;
}
public String forward(int steps) {
while (steps > 0 && !forwardStack.isEmpty()) {
backStack.push(current);
current = forwardStack.pop();
steps--;
}
return current;
}
}#include <stack>
#include <string>
class BrowserHistory {
std::stack<std::string> backStack;
std::stack<std::string> forwardStack;
std::string current;
public:
BrowserHistory(std::string homepage) : current(homepage) {}
void visit(std::string url) {
backStack.push(current);
current = url;
forwardStack = std::stack<std::string>();
}
std::string back(int steps) {
while (!backStack.empty() && steps-- > 0) {
forwardStack.push(current);
current = backStack.top();
backStack.pop();
}
return current;
}
std::string forward(int steps) {
while (!forwardStack.empty() && steps-- > 0) {
backStack.push(current);
current = forwardStack.top();
forwardStack.pop();
}
return current;
}
};class BrowserHistory {
constructor(homepage) {
this.backStack = [];
this.forwardStack = [];
this.current = homepage;
}
visit(url) {
this.backStack.push(this.current);
this.current = url;
this.forwardStack = [];
}
back(steps) {
while (steps > 0 && this.backStack.length) {
this.forwardStack.push(this.current);
this.current = this.backStack.pop();
steps--;
}
return this.current;
}
forward(steps) {
while (steps > 0 && this.forwardStack.length) {
this.backStack.push(this.current);
this.current = this.forwardStack.pop();
steps--;
}
return this.current;
}
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BrowserHistory {
char **backStack;
int backTop;
char **forwardStack;
int forwardTop;
char *current;
} BrowserHistory;
void push(char **stack, int *top, char *url) {
stack[++(*top)] = strdup(url);
}
char* pop(char **stack, int *top) {
return stack[(*top)--];
}
BrowserHistory* browserHistoryCreate(char *homepage) {
BrowserHistory *history = (BrowserHistory*)malloc(sizeof(BrowserHistory));
history->backStack = (char**)malloc(5000 * sizeof(char*));
history->backTop = -1;
history->forwardStack = (char**)malloc(5000 * sizeof(char*));
history->forwardTop = -1;
history->current = strdup(homepage);
return history;
}
void browserHistoryVisit(BrowserHistory* history, char *url) {
push(history->backStack, &history->backTop, history->current);
history->current = strdup(url);
history->forwardTop = -1;
}
char* browserHistoryBack(BrowserHistory* history, int steps) {
for (int i = 0; i < steps && history->backTop >= 0; i++) {
push(history->forwardStack, &history->forwardTop, history->current);
history->current = pop(history->backStack, &history->backTop);
}
return history->current;
}
char* browserHistoryForward(BrowserHistory* history, int steps) {
for (int i = 0; i < steps && history->forwardTop >= 0; i++) {
push(history->backStack, &history->backTop, history->current);
history->current = pop(history->forwardStack, &history->forwardTop);
}
return history->current;
}
void browserHistoryFree(BrowserHistory* history) {
while (history->backTop >= 0) free(pop(history->backStack, &history->backTop));
while (history->forwardTop >= 0) free(pop(history->forwardStack, &history->forwardTop));
free(history->current);
free(history->backStack);
free(history->forwardStack);
free(history);
}using System;
using System.Collections.Generic;
public class BrowserHistory {
private Stack<string> backStack = new Stack<string>();
private Stack<string> forwardStack = new Stack<string>();
private string current;
public BrowserHistory(string homepage) {
current = homepage;
}
public void Visit(string url) {
backStack.Push(current);
current = url;
forwardStack.Clear();
}
public string Back(int steps) {
while (steps > 0 && backStack.Count > 0) {
forwardStack.Push(current);
current = backStack.Pop();
steps--;
}
return current;
}
public string Forward(int steps) {
while (steps > 0 && forwardStack.Count > 0) {
backStack.Push(current);
current = forwardStack.Pop();
steps--;
}
return current;
}
}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.
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.
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.
type BrowserHistory struct {
stk1 []string
stk2 []string
}
func Constructor(homepage string) BrowserHistory {
t := BrowserHistory{[]string{}, []string{}}
t.Visit(homepage)
return t
}
func (this *BrowserHistory) Visit(url string) {
this.stk1 = append(this.stk1, url)
this.stk2 = []string{}
}
func (this *BrowserHistory) Back(steps int) string {
for i := 0; i < steps && len(this.stk1) > 1; i++ {
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
this.stk1 = this.stk1[:len(this.stk1)-1]
}
return this.stk1[len(this.stk1)-1]
}
func (this *BrowserHistory) Forward(steps int) string {
for i := 0; i < steps && len(this.stk2) > 0; i++ {
this.stk1 = append(this.stk1, this.stk2[len(this.stk2)-1])
this.stk2 = this.stk2[:len(this.stk2)-1]
}
return this.stk1[len(this.stk1)-1]
}
/**
* Your BrowserHistory object will be instantiated and called as such:
* obj := Constructor(homepage);
* obj.Visit(url);
* param_2 := obj.Back(steps);
* param_3 := obj.Forward(steps);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach Using a List | Time Complexity: Each operation (visit, back, forward) is O(1) on average due to direct index manipulation or list slicing. |
| Approach Using Two Stacks | Time Complexity: Each call to visit, back, or forward is O(steps) due to operations over respective stacks. |
| Two Stacks | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| List with Current Pointer | O(1) per operation | O(n) | Best for simple implementation using array and index tracking |
| Two Stacks | O(1) per operation | O(n) | When modeling browser navigation explicitly with back and forward stacks |
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.