Design Browser History (Forward/Back)

🎯

Design Browser History (Forward/Back)

mediumLINKED_LISTAmazonGoogleFacebook

Imagine you are building a web browser that allows users to navigate back and forth through their browsing history seamlessly.

💡 This problem is about designing a data structure that mimics browser history navigation. Beginners often struggle because it requires careful handling of forward and backward navigation and truncating forward history when visiting a new page. Think of it like a playlist where you can move back and forth between songs, but if you play a new song after going back, the upcoming songs are removed.

📋

Problem Statement

Design a browser history system that supports visiting new URLs, moving back by a certain number of steps, and moving forward by a certain number of steps. Implement the BrowserHistory class with the following methods: - BrowserHistory(string homepage): Initializes the object with the homepage. - 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. Return the current URL after moving back. - string forward(int steps): Move steps forward in history. Return the current URL after moving forward.

1 ≤ steps ≤ 1001 ≤ url.length ≤ 20At most 5000 calls will be made to visit, back, and forward.

💡

Example

Input"BrowserHistory browserHistory = new BrowserHistory(\"leetcode.com\");\nbrowserHistory.visit(\"google.com\");\nbrowserHistory.visit(\"facebook.com\");\nbrowserHistory.visit(\"youtube.com\");\nbrowserHistory.back(1);\nbrowserHistory.back(1);\nbrowserHistory.forward(1);\nbrowserHistory.visit(\"linkedin.com\");\nbrowserHistory.forward(2);\nbrowserHistory.back(2);\nbrowserHistory.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', 'youtube.com'. Back 1 step to 'facebook.com', back 1 step to 'google.com', forward 1 step to 'facebook.com'. Visit 'linkedin.com' which clears forward history. Forward 2 steps stays at 'linkedin.com' (no forward history). Back 2 steps to 'google.com', back 7 steps to 'leetcode.com' (can't go back further).

• Back steps more than history length → returns earliest page
• Forward steps more than forward history → returns latest page
• Visit after back truncates forward history
• Visit on homepage without any forward or back history

⚠️

Common Mistakes

Not truncating forward history on visit

Forward navigation returns outdated pages

✅ Clear forward history nodes or stack when visiting a new page

Allowing back navigation beyond first page

Index out of bounds or null pointer errors

✅ Clamp back steps to not go before the homepage

Using list slicing in languages where it copies data inefficiently

High time complexity and possible TLE

✅ Use linked list or stacks to avoid copying data

Not updating current pointer correctly after visit

Navigation commands return wrong URLs

✅ Always move current pointer to newly visited node

In two stacks approach, popping all back pages on back operation

Loses history and breaks navigation

✅ Keep at least one page in back stack to represent current page

🧠

Brute Force (Using List and Index Tracking)

💡 This approach uses a simple list to store history and an index pointer to track the current page. It is straightforward and helps understand the problem mechanics before optimizing. Imagine a playlist where the current song is tracked by an index, and visiting a new song removes all songs ahead.

Intuition

Store all visited URLs in a list and keep track of the current position. When visiting a new URL, truncate the forward history and append the new URL. Back and forward operations move the current position pointer accordingly.

Algorithm

1. Initialize a list with the homepage and set current index to 0.
2. On visit(url), truncate the list after current index and append url, then update current index.
3. On back(steps), move current index back by steps but not below 0, return URL at current index.
4. On forward(steps), move current index forward by steps but not beyond last index, return URL at current index.

💡 The main challenge is correctly truncating forward history and updating the current index to reflect navigation.

</>

Code

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.curr = 0

    def visit(self, url: str) -> None:
        self.history = self.history[:self.curr+1]
        self.history.append(url)
        self.curr += 1

    def back(self, steps: int) -> str:
        self.curr = max(0, self.curr - steps)
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        self.curr = min(len(self.history) - 1, self.curr + steps)
        return self.history[self.curr]

# Driver code
if __name__ == '__main__':
    browserHistory = BrowserHistory("leetcode.com")
    browserHistory.visit("google.com")
    browserHistory.visit("facebook.com")
    browserHistory.visit("youtube.com")
    print(browserHistory.back(1))      # facebook.com
    print(browserHistory.back(1))      # google.com
    print(browserHistory.forward(1))   # facebook.com
    browserHistory.visit("linkedin.com")
    print(browserHistory.forward(2))   # linkedin.com
    print(browserHistory.back(2))       # google.com
    print(browserHistory.back(7))       # leetcode.com

Line Notes

self.history = [homepage]Initialize history list with homepage as the first visited URL to start tracking.

self.curr = 0Set current index pointer to the homepage position to track current page.

self.history = self.history[:self.curr+1]Truncate forward history beyond current position before adding new URL to maintain correct navigation.

self.history.append(url)Append the new URL to history after truncation.

self.curr += 1Move current pointer to the newly visited URL to update current page.

self.curr = max(0, self.curr - steps)Move back pointer but do not go below zero to avoid invalid index.

return self.history[self.curr]Return the URL at the current pointer after back or forward navigation.

self.curr = min(len(self.history) - 1, self.curr + steps)Move forward pointer but do not exceed last index to avoid invalid index.

import java.util.*;

class BrowserHistory {
    private List<String> history;
    private int curr;

    public BrowserHistory(String homepage) {
        history = new ArrayList<>();
        history.add(homepage);
        curr = 0;
    }

    public void visit(String url) {
        while(history.size() > curr + 1) {
            history.remove(history.size() - 1);
        }
        history.add(url);
        curr++;
    }

    public String back(int steps) {
        curr = Math.max(0, curr - steps);
        return history.get(curr);
    }

    public String forward(int steps) {
        curr = Math.min(history.size() - 1, curr + steps);
        return history.get(curr);
    }

    // Driver code
    public static void main(String[] args) {
        BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
        browserHistory.visit("google.com");
        browserHistory.visit("facebook.com");
        browserHistory.visit("youtube.com");
        System.out.println(browserHistory.back(1));      // facebook.com
        System.out.println(browserHistory.back(1));      // google.com
        System.out.println(browserHistory.forward(1));   // facebook.com
        browserHistory.visit("linkedin.com");
        System.out.println(browserHistory.forward(2));   // linkedin.com
        System.out.println(browserHistory.back(2));       // google.com
        System.out.println(browserHistory.back(7));       // leetcode.com
    }
}

Line Notes

history = new ArrayList<>();Initialize dynamic array to store URLs for flexible size.

history.add(homepage);Add homepage as the first URL to start history.

while(history.size() > curr + 1)Remove all forward history beyond current position to maintain correct navigation.

history.add(url);Add new visited URL to history.

curr++;Update current pointer after visiting new URL.

curr = Math.max(0, curr - steps);Move back pointer safely without going below zero.

return history.get(curr);Return current URL after back or forward navigation.

curr = Math.min(history.size() - 1, curr + steps);Move forward pointer safely without exceeding last index.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class BrowserHistory {
    vector<string> history;
    int curr;
public:
    BrowserHistory(string homepage) {
        history.push_back(homepage);
        curr = 0;
    }

    void visit(string url) {
        history.resize(curr + 1);
        history.push_back(url);
        curr++;
    }

    string back(int steps) {
        curr = max(0, curr - steps);
        return history[curr];
    }

    string forward(int steps) {
        curr = min((int)history.size() - 1, curr + steps);
        return history[curr];
    }
};

int main() {
    BrowserHistory browserHistory("leetcode.com");
    browserHistory.visit("google.com");
    browserHistory.visit("facebook.com");
    browserHistory.visit("youtube.com");
    cout << browserHistory.back(1) << "\n";      // facebook.com
    cout << browserHistory.back(1) << "\n";      // google.com
    cout << browserHistory.forward(1) << "\n";   // facebook.com
    browserHistory.visit("linkedin.com");
    cout << browserHistory.forward(2) << "\n";   // linkedin.com
    cout << browserHistory.back(2) << "\n";       // google.com
    cout << browserHistory.back(7) << "\n";       // leetcode.com
    return 0;
}

Line Notes

history.push_back(homepage);Initialize vector with homepage as starting point.

curr = 0;Set current index to homepage position.

history.resize(curr + 1);Truncate forward history before adding new URL to maintain correct navigation.

history.push_back(url);Add new visited URL to history.

curr++;Update current pointer after visit.

curr = max(0, curr - steps);Move back pointer safely without going below zero.

return history[curr];Return current URL after back or forward navigation.

curr = min((int)history.size() - 1, curr + steps);Move forward pointer safely without exceeding last index.

class BrowserHistory {
    constructor(homepage) {
        this.history = [homepage];
        this.curr = 0;
    }

    visit(url) {
        this.history = this.history.slice(0, this.curr + 1);
        this.history.push(url);
        this.curr++;
    }

    back(steps) {
        this.curr = Math.max(0, this.curr - steps);
        return this.history[this.curr];
    }

    forward(steps) {
        this.curr = Math.min(this.history.length - 1, this.curr + steps);
        return this.history[this.curr];
    }
}

// Driver code
const browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");
browserHistory.visit("facebook.com");
browserHistory.visit("youtube.com");
console.log(browserHistory.back(1));      // facebook.com
console.log(browserHistory.back(1));      // google.com
console.log(browserHistory.forward(1));   // facebook.com
browserHistory.visit("linkedin.com");
console.log(browserHistory.forward(2));   // linkedin.com
console.log(browserHistory.back(2));       // google.com
console.log(browserHistory.back(7));       // leetcode.com

Line Notes

this.history = [homepage];Initialize history array with homepage as starting point.

this.curr = 0;Set current pointer to homepage index.

this.history = this.history.slice(0, this.curr + 1);Truncate forward history before adding new URL to maintain correct navigation.

this.history.push(url);Add new visited URL to history.

this.curr++;Update current pointer after visit.

this.curr = Math.max(0, this.curr - steps);Move back pointer safely without going below zero.

return this.history[this.curr];Return current URL after back or forward navigation.

this.curr = Math.min(this.history.length - 1, this.curr + steps);Move forward pointer safely without exceeding last index.

⏱

Complexity

TimeO(n) per visit in worst case due to list slicing (copying) in some languages; back and forward operations are O(1) as they only move an index pointer.

SpaceO(n) for storing all visited URLs in the list.

Each visit may truncate the forward history which involves slicing or removing elements, potentially O(n) time. Back and forward operations only update an index pointer, so they run in O(1).

💡 For 5000 operations, worst case slicing could be costly in some languages, but back and forward are very fast since they just move an index.

Interview Verdict: Accepted but not optimal for large inputs due to slicing

This approach is easy to implement and understand but may be inefficient in some languages due to list slicing overhead.

🧠

Doubly Linked List Implementation

💡 Using a doubly linked list allows efficient insertion and deletion without copying or slicing, making visit, back, and forward operations O(1). Think of it like a train where each carriage is a page, and you can move backward or forward along the train. Adding a new carriage after the current one removes all carriages ahead.

Intuition

Represent each page as a node in a doubly linked list. The current page is a pointer to a node. Visiting a new page removes all nodes after current and appends a new node. Back and forward move the current pointer along the list.

Algorithm

1. Create a doubly linked list node class with URL, prev, and next pointers.
2. Initialize the browser history with a node for homepage and set current pointer.
3. On visit(url), remove all nodes after current, create a new node, link it, and move current pointer.
4. On back(steps), move current pointer backward up to steps or until no prev node, return current URL.
5. On forward(steps), move current pointer forward up to steps or until no next node, return current URL.

💡 The key is to maintain correct links and update current pointer without losing history nodes unnecessarily.

</>

Code

class Node:
    def __init__(self, url):
        self.url = url
        self.prev = None
        self.next = None

class BrowserHistory:
    def __init__(self, homepage: str):
        self.curr = Node(homepage)

    def visit(self, url: str) -> None:
        new_node = Node(url)
        self.curr.next = None  # truncate forward history
        new_node.prev = self.curr
        self.curr.next = new_node
        self.curr = new_node

    def back(self, steps: int) -> str:
        while steps > 0 and self.curr.prev:
            self.curr = self.curr.prev
            steps -= 1
        return self.curr.url

    def forward(self, steps: int) -> str:
        while steps > 0 and self.curr.next:
            self.curr = self.curr.next
            steps -= 1
        return self.curr.url

# Driver code
if __name__ == '__main__':
    browserHistory = BrowserHistory("leetcode.com")
    browserHistory.visit("google.com")
    browserHistory.visit("facebook.com")
    browserHistory.visit("youtube.com")
    print(browserHistory.back(1))      # facebook.com
    print(browserHistory.back(1))      # google.com
    print(browserHistory.forward(1))   # facebook.com
    browserHistory.visit("linkedin.com")
    print(browserHistory.forward(2))   # linkedin.com
    print(browserHistory.back(2))       # google.com
    print(browserHistory.back(7))       # leetcode.com

Line Notes

class Node:Define node structure for doubly linked list to store URL and pointers.

self.curr = Node(homepage)Initialize current pointer to homepage node to start history.

self.curr.next = NoneTruncate forward history by removing next references to discard forward pages.

new_node.prev = self.currLink new node back to current node to maintain doubly linked list.

self.curr.next = new_nodeLink current node's next to new node to insert new page.

self.curr = new_nodeMove current pointer to new node after visit to update current page.

while steps > 0 and self.curr.prev:Move back pointer safely until steps exhausted or no previous node.

return self.curr.urlReturn current URL after back or forward navigation.

class BrowserHistory {
    private class Node {
        String url;
        Node prev, next;
        Node(String url) {
            this.url = url;
        }
    }

    private Node curr;

    public BrowserHistory(String homepage) {
        curr = new Node(homepage);
    }

    public void visit(String url) {
        Node newNode = new Node(url);
        curr.next = null; // truncate forward history
        newNode.prev = curr;
        curr.next = newNode;
        curr = newNode;
    }

    public String back(int steps) {
        while (steps > 0 && curr.prev != null) {
            curr = curr.prev;
            steps--;
        }
        return curr.url;
    }

    public String forward(int steps) {
        while (steps > 0 && curr.next != null) {
            curr = curr.next;
            steps--;
        }
        return curr.url;
    }

    public static void main(String[] args) {
        BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
        browserHistory.visit("google.com");
        browserHistory.visit("facebook.com");
        browserHistory.visit("youtube.com");
        System.out.println(browserHistory.back(1));      // facebook.com
        System.out.println(browserHistory.back(1));      // google.com
        System.out.println(browserHistory.forward(1));   // facebook.com
        browserHistory.visit("linkedin.com");
        System.out.println(browserHistory.forward(2));   // linkedin.com
        System.out.println(browserHistory.back(2));       // google.com
        System.out.println(browserHistory.back(7));       // leetcode.com
    }
}

Line Notes

private class Node {Inner class to represent doubly linked list node with URL and pointers.

curr = new Node(homepage);Initialize current pointer to homepage node to start history.

curr.next = null;Truncate forward history by removing next references to discard forward pages.

newNode.prev = curr;Link new node back to current node to maintain doubly linked list.

curr.next = newNode;Link current node's next to new node to insert new page.

curr = newNode;Move current pointer to new node after visit to update current page.

while (steps > 0 && curr.prev != null)Move back pointer safely until steps exhausted or no previous node.

return curr.url;Return current URL after back or forward navigation.

#include <iostream>
#include <string>
using namespace std;

class BrowserHistory {
    struct Node {
        string url;
        Node* prev;
        Node* next;
        Node(string u) : url(u), prev(nullptr), next(nullptr) {}
    };
    Node* curr;
public:
    BrowserHistory(string homepage) {
        curr = new Node(homepage);
    }

    void visit(string url) {
        Node* newNode = new Node(url);
        curr->next = nullptr; // truncate forward history
        newNode->prev = curr;
        curr->next = newNode;
        curr = newNode;
    }

    string back(int steps) {
        while (steps > 0 && curr->prev != nullptr) {
            curr = curr->prev;
            steps--;
        }
        return curr->url;
    }

    string forward(int steps) {
        while (steps > 0 && curr->next != nullptr) {
            curr = curr->next;
            steps--;
        }
        return curr->url;
    }
};

int main() {
    BrowserHistory browserHistory("leetcode.com");
    browserHistory.visit("google.com");
    browserHistory.visit("facebook.com");
    browserHistory.visit("youtube.com");
    cout << browserHistory.back(1) << "\n";      // facebook.com
    cout << browserHistory.back(1) << "\n";      // google.com
    cout << browserHistory.forward(1) << "\n";   // facebook.com
    browserHistory.visit("linkedin.com");
    cout << browserHistory.forward(2) << "\n";   // linkedin.com
    cout << browserHistory.back(2) << "\n";       // google.com
    cout << browserHistory.back(7) << "\n";       // leetcode.com
    return 0;
}

Line Notes

struct Node {Define doubly linked list node structure with URL and pointers.

curr = new Node(homepage);Initialize current pointer to homepage node to start history.

curr->next = nullptr;Truncate forward history by removing next references to discard forward pages.

newNode->prev = curr;Link new node back to current node to maintain doubly linked list.

curr->next = newNode;Link current node's next to new node to insert new page.

curr = newNode;Move current pointer to new node after visit to update current page.

while (steps > 0 && curr->prev != nullptr)Move back pointer safely until steps exhausted or no previous node.

return curr->url;Return current URL after back or forward navigation.

class Node {
    constructor(url) {
        this.url = url;
        this.prev = null;
        this.next = null;
    }
}

class BrowserHistory {
    constructor(homepage) {
        this.curr = new Node(homepage);
    }

    visit(url) {
        const newNode = new Node(url);
        this.curr.next = null; // truncate forward history
        newNode.prev = this.curr;
        this.curr.next = newNode;
        this.curr = newNode;
    }

    back(steps) {
        while (steps > 0 && this.curr.prev !== null) {
            this.curr = this.curr.prev;
            steps--;
        }
        return this.curr.url;
    }

    forward(steps) {
        while (steps > 0 && this.curr.next !== null) {
            this.curr = this.curr.next;
            steps--;
        }
        return this.curr.url;
    }
}

// Driver code
const browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");
browserHistory.visit("facebook.com");
browserHistory.visit("youtube.com");
console.log(browserHistory.back(1));      // facebook.com
console.log(browserHistory.back(1));      // google.com
console.log(browserHistory.forward(1));   // facebook.com
browserHistory.visit("linkedin.com");
console.log(browserHistory.forward(2));   // linkedin.com
console.log(browserHistory.back(2));       // google.com
console.log(browserHistory.back(7));       // leetcode.com

Line Notes

class Node {Define node class for doubly linked list with URL and pointers.

this.curr = new Node(homepage);Initialize current pointer to homepage node to start history.

this.curr.next = null;Truncate forward history by removing next references to discard forward pages.

newNode.prev = this.curr;Link new node back to current node to maintain doubly linked list.

this.curr.next = newNode;Link current node's next to new node to insert new page.

this.curr = newNode;Move current pointer to new node after visit to update current page.

while (steps > 0 && this.curr.prev !== null)Move back pointer safely until steps exhausted or no previous node.

return this.curr.url;Return current URL after back or forward navigation.

⏱

Complexity

TimeO(1) for visit, back, and forward operations since only pointer updates and moves are done without copying data.

SpaceO(n) for storing nodes in doubly linked list, where n is number of visited pages.

Each operation only changes pointers or moves current pointer without copying data, making it efficient and scalable.

💡 This approach scales well for large number of operations due to constant time navigation and no costly copying.

Interview Verdict: Accepted and optimal for interview coding

This is the preferred approach in interviews because it balances clarity and efficiency.

🧠

Two Stacks Approach

💡 Using two stacks to simulate back and forward history is intuitive and efficient, leveraging stack operations to manage navigation. Imagine two piles of cards: one for pages you can go back to, one for pages you can go forward to. Moving back or forward moves cards between piles.

Intuition

Maintain two stacks: one for back history and one for forward history. The current page is the top of the back stack. Visiting a new page pushes it onto the back stack and clears the forward stack. Back pops from back stack to forward stack, forward pops from forward stack to back stack.

Algorithm

1. Initialize back stack with homepage and empty forward stack.
2. On visit(url), push url onto back stack and clear forward stack.
3. On back(steps), pop up to steps from back stack to forward stack, but keep at least one page in back stack, return top of back stack.
4. On forward(steps), pop up to steps from forward stack to back stack, return top of back stack.

💡 The main challenge is ensuring the back stack never becomes empty and correctly moving pages between stacks.

</>

Code

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        self.forward_stack.clear()

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

# Driver code
if __name__ == '__main__':
    browserHistory = BrowserHistory("leetcode.com")
    browserHistory.visit("google.com")
    browserHistory.visit("facebook.com")
    browserHistory.visit("youtube.com")
    print(browserHistory.back(1))      # facebook.com
    print(browserHistory.back(1))      # google.com
    print(browserHistory.forward(1))   # facebook.com
    browserHistory.visit("linkedin.com")
    print(browserHistory.forward(2))   # linkedin.com
    print(browserHistory.back(2))       # google.com
    print(browserHistory.back(7))       # leetcode.com

Line Notes

self.back_stack = [homepage]Initialize back stack with homepage as current page to start history.

self.forward_stack = []Initialize empty forward stack to store forward pages.

self.back_stack.append(url)Add new visited URL to back stack to update current page.

self.forward_stack.clear()Clear forward stack on new visit to discard forward history.

while steps > 0 and len(self.back_stack) > 1Pop from back stack to forward stack but keep at least one page to avoid empty history.

return self.back_stack[-1]Return current page after back or forward navigation.

while steps > 0 and self.forward_stackPop from forward stack to back stack during forward navigation.

import java.util.*;

class BrowserHistory {
    private Deque<String> backStack;
    private Deque<String> forwardStack;

    public BrowserHistory(String homepage) {
        backStack = new ArrayDeque<>();
        forwardStack = new ArrayDeque<>();
        backStack.push(homepage);
    }

    public void visit(String url) {
        backStack.push(url);
        forwardStack.clear();
    }

    public String back(int steps) {
        while (steps > 0 && backStack.size() > 1) {
            forwardStack.push(backStack.pop());
            steps--;
        }
        return backStack.peek();
    }

    public String forward(int steps) {
        while (steps > 0 && !forwardStack.isEmpty()) {
            backStack.push(forwardStack.pop());
            steps--;
        }
        return backStack.peek();
    }

    public static void main(String[] args) {
        BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
        browserHistory.visit("google.com");
        browserHistory.visit("facebook.com");
        browserHistory.visit("youtube.com");
        System.out.println(browserHistory.back(1));      // facebook.com
        System.out.println(browserHistory.back(1));      // google.com
        System.out.println(browserHistory.forward(1));   // facebook.com
        browserHistory.visit("linkedin.com");
        System.out.println(browserHistory.forward(2));   // linkedin.com
        System.out.println(browserHistory.back(2));       // google.com
        System.out.println(browserHistory.back(7));       // leetcode.com
    }
}

Line Notes

backStack = new ArrayDeque<>();Initialize back stack as deque for efficient push/pop operations.

forwardStack = new ArrayDeque<>();Initialize forward stack as deque for efficient push/pop operations.

backStack.push(homepage);Push homepage onto back stack as current page to start history.

backStack.push(url);Push new visited URL onto back stack to update current page.

forwardStack.clear();Clear forward stack on new visit to discard forward history.

while (steps > 0 && backStack.size() > 1)Pop from back stack to forward stack but keep at least one page to avoid empty history.

return backStack.peek();Return current page after back or forward navigation.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class BrowserHistory {
    stack<string> backStack, forwardStack;
public:
    BrowserHistory(string homepage) {
        backStack.push(homepage);
    }

    void visit(string url) {
        backStack.push(url);
        while (!forwardStack.empty()) forwardStack.pop();
    }

    string back(int steps) {
        while (steps > 0 && backStack.size() > 1) {
            forwardStack.push(backStack.top());
            backStack.pop();
            steps--;
        }
        return backStack.top();
    }

    string forward(int steps) {
        while (steps > 0 && !forwardStack.empty()) {
            backStack.push(forwardStack.top());
            forwardStack.pop();
            steps--;
        }
        return backStack.top();
    }
};

int main() {
    BrowserHistory browserHistory("leetcode.com");
    browserHistory.visit("google.com");
    browserHistory.visit("facebook.com");
    browserHistory.visit("youtube.com");
    cout << browserHistory.back(1) << "\n";      // facebook.com
    cout << browserHistory.back(1) << "\n";      // google.com
    cout << browserHistory.forward(1) << "\n";   // facebook.com
    browserHistory.visit("linkedin.com");
    cout << browserHistory.forward(2) << "\n";   // linkedin.com
    cout << browserHistory.back(2) << "\n";       // google.com
    cout << browserHistory.back(7) << "\n";       // leetcode.com
    return 0;
}

Line Notes

stack<string> backStack, forwardStack;Use two stacks to store back and forward history for efficient navigation.

backStack.push(homepage);Push homepage as current page to start history.

backStack.push(url);Push new visited URL onto back stack to update current page.

while (!forwardStack.empty()) forwardStack.pop();Clear forward stack on new visit to discard forward history.

while (steps > 0 && backStack.size() > 1)Pop from back stack to forward stack but keep at least one page to avoid empty history.

return backStack.top();Return current page after back or forward navigation.

while (steps > 0 && !forwardStack.empty())Pop from forward stack to back stack during forward navigation.

class BrowserHistory {
    constructor(homepage) {
        this.backStack = [homepage];
        this.forwardStack = [];
    }

    visit(url) {
        this.backStack.push(url);
        this.forwardStack = [];
    }

    back(steps) {
        while (steps > 0 && this.backStack.length > 1) {
            this.forwardStack.push(this.backStack.pop());
            steps--;
        }
        return this.backStack[this.backStack.length - 1];
    }

    forward(steps) {
        while (steps > 0 && this.forwardStack.length > 0) {
            this.backStack.push(this.forwardStack.pop());
            steps--;
        }
        return this.backStack[this.backStack.length - 1];
    }
}

// Driver code
const browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");
browserHistory.visit("facebook.com");
browserHistory.visit("youtube.com");
console.log(browserHistory.back(1));      // facebook.com
console.log(browserHistory.back(1));      // google.com
console.log(browserHistory.forward(1));   // facebook.com
browserHistory.visit("linkedin.com");
console.log(browserHistory.forward(2));   // linkedin.com
console.log(browserHistory.back(2));       // google.com
console.log(browserHistory.back(7));       // leetcode.com

Line Notes

this.backStack = [homepage];Initialize back stack with homepage as starting page.

this.forwardStack = [];Clear forward stack on new visit to discard forward history.

this.backStack.push(url);Push new visited URL onto back stack to update current page.

while (steps > 0 && this.backStack.length > 1)Pop from back stack to forward stack but keep at least one page to avoid empty history.

return this.backStack[this.backStack.length - 1];Return current page after back or forward navigation.

while (steps > 0 && this.forwardStack.length > 0)Pop from forward stack to back stack during forward navigation.

⏱

Complexity

TimeO(1) amortized for visit, back, and forward operations since each operation involves only stack push/pop operations.

SpaceO(n) for storing history in two stacks, where n is number of visited pages.

Each operation involves only stack push/pop operations which are O(1), making it efficient and scalable.

💡 This approach is easy to implement and efficient, especially if you are comfortable with stacks.

Interview Verdict: Accepted and efficient alternative

This approach is a good alternative if linked list implementation is not preferred or allowed.

📊

All Approaches - One-Glance Tradeoffs

💡 The doubly linked list approach is the best balance of clarity and efficiency and should be your go-to in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (List + Index)	O(n) per visit due to slicing	O(n)	No	N/A	Mention only - easy to explain but inefficient
2. Doubly Linked List	O(1) per operation	O(n)	No	N/A	Preferred approach to code
3. Two Stacks	O(1) amortized	O(n)	No	N/A	Good alternative if stacks are preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force list and index approach to show understanding.Step 3: Explain inefficiencies and propose doubly linked list for O(1) operations.Step 4: Optionally mention two stacks approach as an alternative.Step 5: Code the doubly linked list approach with clear comments.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your ability to design a data structure with efficient navigation, handle edge cases like truncation of forward history, and write clean, bug-free code.

Common Follow-ups

• What if we want to limit history size? → Use a fixed size deque or linked list with eviction.
• Can we optimize space if URLs are large? → Use string interning or compression.

💡 These follow-ups test your ability to extend and optimize your design beyond the basic requirements.

🔍

Pattern Recognition

When to Use

1) Need to design a data structure for navigation history, 2) Support back and forward operations, 3) Need to truncate forward history on new visit, 4) Efficient updates and queries required.

Signature Phrases

visit urlmove back stepsmove forward stepsclear forward history

NOT This Pattern When

Problems that only require simple stacks or queues without forward/back navigation are different.

Similar Problems

Implement Stack using Queues - similar design of data structure with operationsDesign Linked List - foundational for linked list design problemsLRU Cache - involves doubly linked list and hash map for efficient updates

Practice

1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?

easy

A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.

B. Use a greedy approach to pick bits that maximize the decimal value at each step.

C. Traverse the list to build a string of bits, then parse the string as a binary number.

D. Apply dynamic programming to store intermediate decimal values for sublists.

Solution

1. Step 1: Understand the problem constraints

   The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.

2. Step 2: Identify the optimal approach

   Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitwise accumulation matches binary to decimal conversion [OK]

Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]

Common Mistakes:

• Using string concatenation then parsing wastes time and space
• Greedy approaches don't apply to binary number conversion
• Dynamic programming is unnecessary overhead here

2. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Extract all node values into arrays, reorder them, then rebuild the list.

B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.

C. Sort the entire linked list using merge sort and then split at value x.

D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   In-place rearrangement achieves O(n) time and O(1) space [OK]

Hint: In-place pointer rearrangement is O(1) space [OK]

Common Mistakes:

• Assuming sorting is needed to partition
• Using extra arrays or lists increases space
• Believing two separate lists always use constant space

3. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?

medium

A. O(n log n) due to bit shifts at each node

B. O(n^2) because recursion stack causes repeated computations

C. O(n) because each node is visited once with constant work

D. O(n) time but O(n^2) space due to recursion stack

Solution

1. Step 1: Analyze time per node

   Each node is processed once, performing a constant number of bit operations (shift and OR).

2. Step 2: Consider recursion overhead

   Recursion depth is n, but no repeated computations occur; each call does O(1) work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Bit shifts are O(1) operations, not O(log n) [OK]

Common Mistakes:

• Assuming bit shifts cost O(log n)
• Confusing recursion stack space with time complexity
• Thinking recursion causes repeated work

4. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:

medium

A. Line assigning curr.next.random = curr.random.next misses null check for curr.random

B. In Step 3, copy_curr is never advanced, causing incorrect separation

C. In Step 1, new_node is linked incorrectly to curr.next

D. The function returns copy_head before fully separating the lists

Solution

1. Step 1: Analyze Step 3 separation loop

   copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.

2. Step 2: Identify fix

   Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing copy_curr, copied list remains partially linked [OK]

Hint: Check if both original and copy pointers advance in separation loop [OK]

Common Mistakes:

• Forgetting to advance copy_curr in separation
• Assuming random pointer null checks are missing (they are present)
• Mislinking new_node in Step 1 (correct here)

5. The following code attempts to reorder a linked list using the recursive approach. Identify the line containing the subtle bug that can cause infinite loops or cycles when traversing the reordered list.

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            # Missing termination here
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

medium

A. Line with 'if not back: return True' -- base case incorrect

B. Line with 'if front[0] == back or front[0].next == back:' -- missing back.next = None

C. Line with 'front[0].next = back' -- incorrect pointer assignment

D. Line with 'front[0] = tmp' -- front pointer update is wrong

Solution

1. Step 1: Identify termination condition

   The condition checking if front meets back must terminate the list by setting back.next = None.

2. Step 2: Locate missing termination

   Line with 'if front[0] == back or front[0].next == back:' lacks 'back.next = None', causing cycles.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing null termination leads to infinite traversal [OK]

Hint: Termination must set back.next = None to avoid cycles [OK]

Common Mistakes:

• Forgetting to null-terminate reordered list
• Misplacing pointer updates
• Incorrect base case handling