Design Browser History - Practice Coding Problems

Design Browser History - Problem

Array Linked List Stack Design Doubly-Linked List Data Stream Medium

You have a browser with one tab where you start on the homepage and you can visit another URL, get back in the history a number of steps, or move forward in the history a number of steps.

Implement the BrowserHistory class:

BrowserHistory(string homepage): Initializes the object with the homepage of the browser.
void visit(string url): Visits url from the current page. It clears up all the forward history.
string back(int steps): Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps): Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Input & Output

Example 1 — Basic Browser Navigation

$ Input: operations = ["BrowserHistory","visit","visit","visit","back","back","forward"], parameters = [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[2]]

› Output: [null,null,null,null,"facebook.com","leetcode.com","facebook.com"]

💡 Note: Initialize with leetcode.com, visit google.com, facebook.com, youtube.com. Back 1 step to facebook.com, back 1 more to leetcode.com, forward 2 steps to facebook.com

Example 2 — Forward History Cleared

$ Input: operations = ["BrowserHistory","visit","back","visit","forward"], parameters = [["home.com"],["page1.com"],[1],["page2.com"],[1]]

› Output: [null,null,"home.com",null,"page2.com"]

💡 Note: Start at home.com, visit page1.com, back to home.com, visit page2.com (clears page1.com), forward stays at page2.com

Example 3 — Boundary Navigation

$ Input: operations = ["BrowserHistory","back","forward"], parameters = [["start.com"],[5],[5]]

› Output: [null,"start.com","start.com"]

💡 Note: Only one page in history, so both back 5 steps and forward 5 steps return start.com

Constraints

1 ≤ homepage.length ≤ 20
1 ≤ url.length ≤ 20
1 ≤ steps ≤ 100
homepage and url consist of '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.

Visualization

Tap to expand

Understanding the Visualization

Initialize

Start with homepage in history array at index 0

Visit Pages

Add new URLs to history, clear forward history when visiting

Navigate

Use back/forward to move current index within bounds

Key Takeaway

🎯 Key Insight: Use array with current index to track position, clear forward history when visiting new pages

Asked in

G Google 15 M Microsoft 12 a Amazon 8 Apple 6

The key insight is to maintain a dynamic array of URLs with a current index pointer. When visiting new pages, clear forward history by truncating the array. Best approach uses array with index tracking: Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Array with Current Index	O(1)	O(n)	Store URLs in array and track current position with index
Dynamic Array with Capacity Management	O(1)	O(n)	Optimize memory usage by managing array capacity more efficiently

Array with Current Index — Algorithm Steps

Step 1: Initialize array with homepage and set current index to 0
Step 2: For visit(), add URL after current position and clear forward history
Step 3: For back(), move index backward within bounds
Step 4: For forward(), move index forward within bounds

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create array with homepage at index 0

Visit URLs

Add new URLs and update current index

Navigate

Move current index for back/forward operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char history[1000][101];  // Max 1000 URLs, each up to 100 chars
    int current;
    int size;
} BrowserHistory;

BrowserHistory* browserHistoryCreate(char* homepage) {
    BrowserHistory* obj = (BrowserHistory*)malloc(sizeof(BrowserHistory));
    strcpy(obj->history[0], homepage);
    obj->current = 0;
    obj->size = 1;
    return obj;
}

void browserHistoryVisit(BrowserHistory* obj, char* url) {
    // Clear forward history and add new URL
    obj->current++;
    obj->size = obj->current + 1;
    strcpy(obj->history[obj->current], url);
}

char* browserHistoryBack(BrowserHistory* obj, int steps) {
    obj->current = (obj->current - steps > 0) ? obj->current - steps : 0;
    return obj->history[obj->current];
}

char* browserHistoryForward(BrowserHistory* obj, int steps) {
    int maxPos = obj->size - 1;
    obj->current = (obj->current + steps < maxPos) ? obj->current + steps : maxPos;
    return obj->history[obj->current];
}

void browserHistoryFree(BrowserHistory* obj) {
    free(obj);
}

int main() {
    // For this implementation, we'll handle a basic test case
    BrowserHistory* browser = browserHistoryCreate("leetcode.com");
    
    browserHistoryVisit(browser, "google.com");
    browserHistoryVisit(browser, "facebook.com");
    browserHistoryVisit(browser, "youtube.com");
    
    printf("[null,null,null,null,\"%s\",\"%s\",\"%s\"]\n", 
           browserHistoryBack(browser, 1),
           browserHistoryBack(browser, 1), 
           browserHistoryForward(browser, 2));
    
    browserHistoryFree(browser);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

All operations are constant time - array access and index updates

✓ Linear Growth

Space Complexity

O(n)

Store up to n URLs in the history array where n is number of unique visits

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array with Current Index — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler