LeetCode 1472 - Design Browser History

LeetCode Problem 1472

Difficulty: 🟡 Medium
Topics: Array, Linked List, Stack, Design, Doubly-Linked List, Data Stream

Solution

Problem Understanding

The problem is asking us to simulate a single-tab browser with a history mechanism. You start on a homepage, and from there, you can visit new URLs, backtrack a certain number of steps, or forward a certain number of steps.

The inputs consist of method calls: BrowserHistory(homepage) initializes the browser with the homepage URL, visit(url) navigates to a new page and clears any forward history, back(steps) moves back in history up to steps times, and forward(steps) moves forward in history up to steps times. The output for back and forward is always the current URL after moving.

Constraints indicate the inputs are small strings of length up to 20, steps can be at most 100, and there can be up to 5000 calls. This means we can afford to store the full history explicitly. Edge cases include attempting to move back or forward more steps than exist in the history, visiting a new page after moving back (which should discard forward history), and repeated visits to the same URL.

Approaches

A brute-force approach would be to maintain a list of visited URLs and a pointer to the current index. On each visit(url), you append the URL and remove any URLs beyond the current pointer. On back(steps) or forward(steps), you adjust the pointer accordingly. This works correctly but can be inefficient if slicing the list repeatedly to remove forward history.

The optimal approach is to use a dynamic array (or slice in Go) with a current pointer without deleting forward elements physically. We just track the effective length of the history after each visit. This avoids expensive list operations and keeps all operations O(1) in the worst case.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per visit in worst case	O(n)	List slice operations may be expensive when clearing forward history
Optimal	O(1) per operation	O(n)	Array/list with a pointer and effective length tracking, avoids slicing

Algorithm Walkthrough

1. Initialize the browser with a list containing the homepage and set a pointer current to index 0. Also maintain a variable last to track the last valid page in the current history.
2. When visit(url) is called, increment current by 1, overwrite the element at that index with url, and set last equal to current. This ensures forward history is effectively discarded without physically removing elements.
3. When back(steps) is called, move current backward by steps, but do not go below 0. Return the URL at the current pointer.
4. When forward(steps) is called, move current forward by steps, but do not go beyond last. Return the URL at the current pointer.

Why it works: By maintaining the current pointer and the last index, we ensure the browser always returns the correct page for back and forward operations. Forward history is logically discarded when visiting a new page, which is handled by updating last.

Python Solution

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.current = 0
        self.last = 0

    def visit(self, url: str) -> None:
        self.current += 1
        if self.current < len(self.history):
            self.history[self.current] = url
        else:
            self.history.append(url)
        self.last = self.current

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

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

This implementation uses a single list history to store URLs and two pointers: current for the active page and last for the end of valid history. On visit, forward history is overwritten or extended. back and forward simply adjust current within valid bounds.

Go Solution

type BrowserHistory struct {
	history []string
	current int
	last    int
}

func Constructor(homepage string) BrowserHistory {
	return BrowserHistory{
		history: []string{homepage},
		current: 0,
		last:    0,
	}
}

func (this *BrowserHistory) Visit(url string) {
	this.current++
	if this.current < len(this.history) {
		this.history[this.current] = url
	} else {
		this.history = append(this.history, url)
	}
	this.last = this.current
}

func (this *BrowserHistory) Back(steps int) string {
	this.current -= steps
	if this.current < 0 {
		this.current = 0
	}
	return this.history[this.current]
}

func (this *BrowserHistory) Forward(steps int) string {
	this.current += steps
	if this.current > this.last {
		this.current = this.last
	}
	return this.history[this.current]
}

The Go implementation mirrors Python. The main difference is that slices are used instead of dynamic arrays, and bounds checks require explicit comparisons instead of using max or min functions.

Worked Examples

Example: ["leetcode.com","google.com","facebook.com","youtube.com"] with operations:

Operation	Current	Last	History
init	0	0	["leetcode.com"]
visit google.com	1	1	["leetcode.com","google.com"]
visit facebook.com	2	2	["leetcode.com","google.com","facebook.com"]
visit youtube.com	3	3	["leetcode.com","google.com","facebook.com","youtube.com"]
back 1	2	3	["leetcode.com","google.com","facebook.com","youtube.com"]
back 1	1	3	same
forward 1	2	3	same
visit linkedin.com	3	3	["leetcode.com","google.com","facebook.com","linkedin.com"]
forward 2	3	3	same
back 2	1	3	same
back 7	0	3	same

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per operation	All operations are pointer adjustments and optional list append/overwrite
Space	O(n)	History list stores each visited URL

History is stored efficiently, and no unnecessary slicing is performed, keeping operations constant time.

Test Cases

# Basic usage
browser = BrowserHistory("leetcode.com")
browser.visit("google.com")
browser.visit("facebook.com")
browser.visit("youtube.com")
assert browser.back(1) == "facebook.com"  # move back one step
assert browser.back(1) == "google.com"    # move back one step
assert browser.forward(1) == "facebook.com"  # forward one step
browser.visit("linkedin.com")
assert browser.forward(2) == "linkedin.com"  # cannot move forward
assert browser.back(2) == "google.com"       # move back two steps
assert browser.back(7) == "leetcode.com"     # move back only available steps

# Edge case: single page history
single_page = BrowserHistory("home")
assert single_page.back(1) == "home"
assert single_page.forward(1) == "home"
single_page.visit("page1")
assert single_page.back(1) == "home"
assert single_page.forward(1) == "page1"

# Repeated visits
repeat = BrowserHistory("a.com")
repeat.visit("b.com")
repeat.visit("b.com")
repeat.back(1)
assert repeat.forward(1) == "b.com"

Test	Why
Problem statement example	Validates general behavior with back, forward, and visit
Single page history	Ensures back/forward does not go out of bounds
Repeated visits	Confirms forward history is correctly overwritten when visiting same page

Edge Cases

One edge case occurs when trying to move back more steps than exist in history. The implementation correctly clamps the current pointer to zero. Another edge case is visiting a new page after moving back; all forward history beyond the current index is discarded by updating last. A third edge case is repeatedly visiting the same page; the algorithm handles it naturally by overwriting or appending, ensuring no duplication errors in forward/back operations. These edge cases demonstrate that the algorithm is robust under all valid constraints.