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 <= 201 <= url.length <= 201 <= steps <= 100homepage and url consist of '.' or lower case English letters.5000 calls will be made to visit, back, and forward.The #1472 Design Browser History problem focuses on simulating how a browser manages navigation between pages using operations like visit, back, and forward. The core challenge is maintaining history while efficiently moving backward and forward through visited pages.
A common approach is to model the navigation history using a doubly linked list. Each node represents a webpage, with pointers to both the previous and next pages. This allows constant-time movement in either direction and makes it easy to discard forward history when a new page is visited.
Another practical design uses two stacks or an array with a pointer. The back stack stores previously visited pages while the forward stack stores pages available for forward navigation. Visiting a new page clears the forward stack.
Both designs ensure efficient updates and navigation, typically achieving O(1) time per operation with linear space proportional to the number of visited pages.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Doubly Linked List | O(1) per operation | O(n) |
| Two Stacks | O(1) per operation | O(n) |
| Array with Pointer | O(1) average per operation | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use two stacks: one for back history, and one for forward history. You can simulate the functions by popping an element from one stack and pushing it into the other.
Can you improve program runtime by using a different data structure?
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.
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.
1#include <vector>
2#include <string>
3
4class BrowserHistory {
5 std::vector<std::string> history;
6 int current;
7public:
8 BrowserHistory(std::string homepage) {
9 history.push_back(homepage);
10 current = 0;
11 }
12
13 void visit(std::string url) {
14 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];
}
};The C++ implementation uses a vector to store the browsing history. Similar to other solutions, we maintain a 'current' index. On visiting a new URL, we truncate the vector and add the new page. The 'back' and 'forward' methods adjust the position logically.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, design-based data structure problems like this frequently appear in technical interviews at companies such as Amazon, Google, and Meta. They test understanding of stacks, linked lists, and system design thinking.
A doubly linked list is often considered the most natural structure because it supports efficient movement in both directions. However, two stacks or a dynamic array with a pointer can also implement the same behavior effectively.
An optimal approach is to use a doubly linked list or two stacks to represent backward and forward navigation. These structures allow constant-time updates for visiting, going back, and moving forward between pages.
When a user visits a new page after going back, the previous forward navigation path becomes invalid. To mimic real browser behavior, the forward history must be removed before adding the new page to the history.
In JavaScript, two arrays serve as stacks. When visiting a new site, the forward history is cleared. The back and forward methods modify these stacks to simulate historical navigation.