1472. Design Browser History

MediumStackDesignArrayLinked ListData StreamDoubly-Linked List

Problem Description

In this LeetCode problem, we're asked to simulate a browser history where you can visit new URLs, move back a certain number of steps in your browser history, or move forward a certain number of steps in the history. This needs to be done through implementing a BrowserHistory class with specific functionalities:

BrowserHistory(string homepage): Initializes a BrowserHistory object with a given homepage URL.
void visit(string url): Simulates visiting a new URL from the current page, which erases all forward history.
string back(int steps): Moves steps back in the history, but only up to how many URLs are behind the current one. It returns the URL you land on.
string forward(int steps): Moves steps forward in the history, but only up to how many URLs are ahead of the current one. Similarly, it returns the URL you land on.

Some limitations have been placed on the inputs to keep the problem bounded:

URL and homepage strings will only contain lowercase English letters and the period character, and their lengths will range between 1 and 20 characters.
The steps parameter in the back and forward methods will be between 1 and 100.
The visit, back, and forward methods will be called at most 5000 times in total.

Intuition

To simulate browser history, we need a way to keep track of visited URLs and navigate back and forth. We can use two stacks to model the back and forward browser functionality. The main stack (stk1) keeps track of the browsing history where the top of the stack is the current page being viewed. Another stack (stk2) is used to keep track of the pages that have been gone back from, enabling us to navigate forward.

Visit: When visiting a new URL, we push it onto stk1, representing that it is now the current page. We also clear stk2, because visiting a new page after going back in history means that you can no longer go forward to the pages that were ahead of your previous current page (this reflects real browser behavior).
Back: When moving back, we pop URLs from stk1 and push them onto stk2, decrementing the steps each time until we either reach the desired number of steps or can't go back further (because we've reached the homepage). The top of stk1 after these operations gives us the current page.
Forward: The forward action is similar to back but in reverse — we pop from stk2 and push onto stk1, moving the current page forward in history. Again, we do this until we've completed the desired number of steps or we've reached the most recent page (when stk2 is empty).

This approach uses stacks to effectively traverse through the history, ensuring that the order of navigation is maintained and that we have an efficient way to move back and forward through the pages visited.

Learn more about Stack, Linked List and Data Stream patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The solution provided uses two stacks (stk1 and stk2) for tracking the browser history. Let's walk through the implementation of each method and how they manipulate these stacks to satisfy the requirements.

Constructor: `BrowserHistory(string homepage)`

When a new BrowserHistory object is created, it is initialized with the homepage. This is done by calling the visit method with the homepage URL as the argument, establishing the starting point of our browser history. At this point, stk1 will contain the homepage URL, and stk2 will be empty as there's no forward or backward history.

Visit Method: `visit(string url)`

When visiting a new URL, we push the URL onto stk1 (the stack representing our browse history) and clear stk2 (forward history). Clearing stk2 is essential because any forward history is erased as per the real-life browser behavior whenever you visit a new page after navigating back. The current URL is now at the top of stk1.

Back Method: `back(int steps)`

This method simulates the action of the 'Back' button in a browser. When invoked, it checks if we can move back the given number of steps. As long as there are more than one URLs in stk1 (we're not at the homepage), it transfers the top URL to stk2 (simulating movement back in history). It reduces steps by 1 each time this transfer happens. Finally, when steps reach zero or cannot go back further, it returns the current URL, which is at the top of stk1.

Forward Method: `forward(int steps)`

This method simulates pressing the 'Forward' button in a browser, the reverse of the back method. While there are items in stk2 (i.e., there's forward history to traverse) and steps is not zero, it moves URLs from stk2 back to stk1. This process effectively steps back through the history forward. Once steps have been depleted or there is no more forward history (stk2 is empty), it returns the URL at the top of stk1, which is now the current page.

The overall pattern this solution follows is a classic use of stack data structures for managing history in such a way that the order of movement back and forth is naturally maintained. Stacks are ideal because they follow a last-in-first-out (LIFO) principle that directly aligns with the action of navigating backward and forward through a linear browsing history.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Example Walkthrough

Let's take an example to illustrate how the BrowserHistory class and its methods work in practice:

Suppose we initialize the browser history with the homepage:

1browserHistory = BrowserHistory("leetcode.com")

After this step, stk1 contains ["leetcode.com"] and stk2 is empty.

We visit a new URL "google.com":
```
1browserHistory.visit("google.com")
```
stk1 is now ["leetcode.com", "google.com"], and stk2 remains empty, as visiting a new URL doesn't involve moving back or forward.
Let's visit another URL "facebook.com":
```
1browserHistory.visit("facebook.com")
```
Now, stk1 has ["leetcode.com", "google.com", "facebook.com"], and stk2 is still empty.
We decide to move back by 1 step in the history:
```
1current_url = browserHistory.back(1)
```
This transfers "facebook.com" from stk1 to stk2, leaving us with stk1 = ["leetcode.com", "google.com"] and stk2 = ["facebook.com"]. The current_url is "google.com".
We move back again, this time by 2 steps:
```
1current_url = browserHistory.back(2)
```
We can only move back by 1 step because we're at "google.com" and can't go further back than "leetcode.com", so stk1 becomes ["leetcode.com"] and stk2 transforms to ["google.com", "facebook.com"]. The current_url is "leetcode.com".
Now we move forward by 1 step:
```
1current_url = browserHistory.forward(1)
```
"google.com" is popped from stk2 and pushed onto stk1, resulting in stk1 = ["leetcode.com", "google.com"] and stk2 = ["facebook.com"]. The current_url becomes "google.com".
If we visit a new site "youtube.com":
```
1browserHistory.visit("youtube.com")
```
stk1 becomes ["leetcode.com", "google.com", "youtube.com"] and stk2 is cleared out, signifying that the forward history is erased due to this new visit. stk2 = [].
Finally, if we try to go forward by 2 steps:
```
1current_url = browserHistory.forward(2)
```
We can't move forward because stk2 is empty, hence the current_url remains "youtube.com".

So our final stacks look like this: stk1 = ["leetcode.com", "google.com", "youtube.com"] and stk2 = []. This series of actions demonstrates how the methods work together to simulate real-world browser history navigation.

Solution Implementation

1class BrowserHistory:
2    def __init__(self, homepage: str):
3        # Initialize stack for backward history and forward history
4        # Stack 1 keeps all backward history from the current page.
5        # Stack 2 is cleared every time a new page is visited and keeps pages for potential forward navigation.
6        self.backward_history = []
7        self.forward_history = []
8        # Visit the homepage, which clears forward history and records the provided homepage.
9        self.visit(homepage)
10
11    def visit(self, url: str) -> None:
12        # Record the visited URL and clear the forward history, because new navigation breaks the forward path.
13        self.backward_history.append(url)
14        self.forward_history.clear()
15
16    def back(self, steps: int) -> str:
17        # Move back in the history the given number of steps, if possible,
18        # moving URLs from backward to forward history.
19        while steps and len(self.backward_history) > 1:
20            # Move the current URL to the forward history.
21            self.forward_history.append(self.backward_history.pop())
22            # Decrease the steps we need to go back.
23            steps -= 1
24        # Return the current URL after moving back.
25        return self.backward_history[-1]
26
27    def forward(self, steps: int) -> str:
28        # Go forward in the history the given number of steps if there are enough pages in forward history,
29        # moving URLs back to backward history.
30        while steps and self.forward_history:
31            # Move one URL from forward history back to backward history.
32            self.backward_history.append(self.forward_history.pop())
33            # Decrease the steps we need to go forward.
34            steps -= 1
35        # Return the current URL after moving forward.
36        return self.backward_history[-1]
37
38# Your BrowserHistory object will be instantiated and called as such:
39# obj = BrowserHistory(homepage)
40# obj.visit(url)
41# param_2 = obj.back(steps)
42# param_3 = obj.forward(steps)
43

1class BrowserHistory {
2    // Deques for navigating backward and forward
3    private Deque<String> historyStack = new ArrayDeque<>();
4    private Deque<String> forwardStack = new ArrayDeque<>();
5
6    // Constructor stores the homepage and clears the forward history
7    public BrowserHistory(String homepage) {
8        visit(homepage);
9    }
10
11    // Method to visit a new URL: Pushes the current URL to the history stack
12    // and clears the forward history
13    public void visit(String url) {
14        historyStack.push(url);
15        forwardStack.clear(); // Clear forward navigation because a new page is visited
16    }
17
18    // Method to move 'steps' back in the browser history
19    public String back(int steps) {
20        // Pop from history stack and push into forward stack while more than 1 page is in history
21        // and allowed steps are remaining
22        while (steps > 0 && historyStack.size() > 1) {
23            forwardStack.push(historyStack.pop());
24            steps--;
25        }
26        return historyStack.peek(); // Return the current URL
27    }
28
29    // Method to move 'steps' forward in the browser history
30    public String forward(int steps) {
31        // Pop from forward stack and push into history stack while there are pages in forward history
32        // and allowed steps are remaining
33        while (steps > 0 && !forwardStack.isEmpty()) {
34            historyStack.push(forwardStack.pop());
35            steps--;
36        }
37        return historyStack.peek(); // Return the current URL
38    }
39}
40
41// Example on how to use the BrowserHistory class:
42/*
43BrowserHistory browserHistory = new BrowserHistory("www.homepage.com");
44browserHistory.visit("www.page1.com");
45String backPage = browserHistory.back(1); // Returns to 'www.homepage.com'
46String forwardPage = browserHistory.forward(1); // Goes forward to 'www.page1.com'
47*/
48

1#include <stack>
2#include <string>
3
4// The BrowserHistory class keeps track of browser navigation history.
5class BrowserHistory {
6private:
7    std::stack<std::string> backHistory;  // Stack to manage back navigation.
8    std::stack<std::string> forwardHistory; // Stack to manage forward navigation.
9
10public:
11    // Constructor initializes the browser history with the homepage.
12    BrowserHistory(std::string homepage) {
13        visit(homepage);
14    }
15
16    // The visit method navigates to a new URL, clears the forward history, and pushes the URL onto the back stack.
17    void visit(std::string url) {
18        backHistory.push(url);
19        // Clear the forward stack since we visited a new URL.
20        forwardHistory = std::stack<std::string>(); 
21    }
22
23    // The back method moves back 'steps' times in the history unless we are at the first page.
24    // It returns the current URL after going back.
25    std::string back(int steps) {
26        // Go back at most steps times and make sure not to go past the initial page.
27        while (steps && backHistory.size() > 1) {
28            forwardHistory.push(backHistory.top());
29            backHistory.pop();
30            --steps;
31        }
32        return backHistory.top(); // Return the current URL.
33    }
34
35    // The forward method moves forward 'steps' times in the history if possible.
36    // It returns the current URL after going forward.
37    std::string forward(int steps) {
38        // Go forward at most steps times and only if there is forward history available.
39        while (steps && !forwardHistory.empty()) {
40            backHistory.push(forwardHistory.top());
41            forwardHistory.pop();
42            --steps;
43        }
44        return backHistory.top(); // Return the current URL.
45    }
46};
47
48/* Usage of the BrowserHistory class
49BrowserHistory* browserHistory = new BrowserHistory("homepage");
50browserHistory->visit("url1");
51browserHistory->visit("url2");
52std::string currentUrl = browserHistory->back(1);
53currentUrl = browserHistory->forward(1);
54delete browserHistory; // Don't forget to delete the object to avoid memory leak.
55*/
56

1let backHistory: string[] = []; // Array to manage back navigation.
2let forwardHistory: string[] = []; // Array to manage forward navigation.
3
4// The visit function navigates to a new URL, clears the forward history, and pushes the URL onto the back stack.
5function visit(url: string): void {
6    backHistory.push(url);
7    forwardHistory = []; // Clear the forward history since we visited a new URL.
8}
9
10// The back function moves back 'steps' times in the history unless we are at the first page.
11// It returns the current URL after going back.
12function back(steps: number): string {
13    // Go back at most 'steps' times and make sure not to go past the initial page.
14    while (steps > 0 && backHistory.length > 1) {
15        forwardHistory.push(backHistory.pop()!); // Assert non-null as we know there's more than one item.
16        steps--;
17    }
18    return backHistory[backHistory.length - 1]; // Return the current URL.
19}
20
21// The forward function moves forward 'steps' times in the history if possible.
22// It returns the current URL after going forward.
23function forward(steps: number): string {
24    // Go forward at most 'steps' times and only if there is forward history available.
25    while (steps > 0 && forwardHistory.length > 0) {
26        backHistory.push(forwardHistory.pop()!); // Assert non-null as the length check ensures the item exists.
27        steps--;
28    }
29    return backHistory[backHistory.length - 1]; // Return the current URL.
30}
31
32// Usage of the global functions
33visit("homepage");
34visit("url1");
35visit("url2");
36let currentUrl: string = back(1);
37currentUrl = forward(1);
38// No need for a delete operation since there's no object allocation.
39

Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Time and Space Complexity

The time complexity for each operation in the BrowserHistory class is as follows:

visit method: The time complexity is O(1) for appending a URL to stk1 and O(n) for clearing stk2, where n is the number of elements in stk2. However, since the clear operation assigns stk2 a new empty list, it can be considered O(1) in practice.
back method: The worst-case time complexity is O(steps), which occurs when you move steps times back in the history. However, it cannot exceed n - 1 where n is the number of elements in stk1. This is because you can only move back as many times as there are pages in stk1 minus the current page.
forward method: The time complexity is O(steps) similarly to the back method, with the maximum number of steps being limited by the number of pages in stk2.

The space complexity is the sum of the space taken by stk1 and stk2:

Space complexity: O(m + k) where m is the number of total pages ever visited and k is the number of pages that have been moved back from using the back method. Note that k <= m. Therefore, we can simplify the space complexity to O(m) which is dictated by the total number of unique pages visited throughout the use of the browser history.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1472. Design Browser History

Problem Description

Intuition

Solution Approach

Constructor: BrowserHistory(string homepage)

Visit Method: visit(string url)

Back Method: back(int steps)

Forward Method: forward(int steps)

Example Walkthrough

Solution Implementation

Time and Space Complexity

Constructor: `BrowserHistory(string homepage)`

Visit Method: `visit(string url)`

Back Method: `back(int steps)`

Forward Method: `forward(int steps)`