Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Design Browser History (Forward/Back)

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (List + Index)O(n) per visit due to slicingO(n)NoN/AMention only - easy to explain but inefficient
2. Doubly Linked ListO(1) per operationO(n)NoN/APreferred approach to code
3. Two StacksO(1) amortizedO(n)NoN/AGood 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/5)
1. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Use a recursive approach that reverses k nodes at a time and recurses on the rest, relying on call stack for reversal.
B. Apply a dynamic programming approach to store reversed sublists and combine them for the final result.
C. Iteratively traverse the list, reversing each group of k nodes using a helper function, and reconnect groups with pointer manipulation.
D. Use a greedy approach that reverses nodes whenever possible without checking group boundaries.

Solution

  1. Step 1: Understand problem constraints

    The problem requires reversing nodes in groups of k, preserving the order of leftover nodes if fewer than k remain.
  2. Step 2: Evaluate approaches

    Recursive approach (A) uses extra stack space and risks overflow; DP (B) is not applicable; greedy (D) fails on partial groups. Iterative with helper (C) reverses groups efficiently with O(1) space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Iterative helper method is standard optimal solution [OK]
Hint: Iterative helper reversal is optimal for O(1) space [OK]
Common Mistakes:
  • Confusing recursion with iterative approach
  • Assuming DP applies to linked list reversal
  • Ignoring partial group handling
2. 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
3. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?
medium
A. O(n), because traversal is needed to find the tail
B. O(log n), because the list is balanced using sentinel nodes
C. O(1), because the tail pointer allows direct access to the last node
D. O(n), because updating the size requires traversal

Solution

  1. Step 1: Identify operation steps

    addAtTail uses the tail pointer to append a new node directly without traversal.
  2. Step 2: Analyze complexity

    Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Tail pointer eliminates traversal, so addAtTail is constant time [OK]
Hint: Tail pointer enables O(1) tail insertions [OK]
Common Mistakes:
  • Assuming traversal needed to find tail
  • Confusing size update cost
  • Thinking sentinel nodes balance list
4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause incorrect backward traversal of the flattened list?
medium
A. Line: Missing child.prev = curr assignment
B. Line: if curr.next: curr.next.prev = tail
C. Line: curr.next = child
D. Line: tail.next = curr.next

Solution

  1. Step 1: Identify pointer updates

    After connecting curr.next to child, child's prev pointer must point back to curr.
  2. Step 2: Locate missing update

    The code misses setting child.prev = curr, breaking backward links and causing incorrect prev traversal.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without child.prev update, backward traversal fails [OK]
Hint: Always update both next and prev pointers when splicing lists [OK]
Common Mistakes:
  • Forgetting to update child's prev pointer
  • Assuming tail.next update fixes all pointers
  • Confusing next and prev pointer roles
5. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?
medium
A. O(n) -- recursion stack uses space proportional to list length
B. O(1) -- only constant extra pointers used
C. O(log n) -- recursion depth is halved each call
D. O(n^2) -- due to repeated pointer updates in recursion

Solution

  1. Step 1: Identify recursion depth

    The helper function recurses once per node, so recursion depth is n.
  2. Step 2: Calculate space usage

    Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack proportional to list length [OK]
Hint: Recursion depth equals list length -> O(n) space [OK]
Common Mistakes:
  • Assuming constant space due to in-place changes
  • Confusing recursion depth with log n
  • Overestimating to quadratic space
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard