Abstract / Summary

Design a browser history system that supports visiting new pages, going back and forth, and retrieving the current page.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 78% (400k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The BrowserHistory class models a simple linear navigation history for a web browser. It maintains an ordered collection of visited URLs and a cursor indicating the current page. The implementation provides four public operations: construction with a home page, visiting a new URL, moving backward a given number of steps, and moving forward a given number of steps. Each operation updates the internal state in place and returns the URL at the new cursor position when appropriate.

Core Components

Constructor

The initializer creates the history container and positions the cursor at the start.

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

A list containing the initial page is allocated, and the position index pos is set to 0, pointing to that page.

Visiting a New URL

When a new URL is visited, any forward history beyond the current cursor is discarded, the new URL is appended, and the cursor advances.

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

The conditional slice operation removes stale entries that would otherwise be reachable by a forward navigation. The append operation adds the new page, and the cursor is incremented to reference it.

Moving Backward

The back method reduces the cursor by the requested number of steps, clamping it at the start of the list to avoid underflow, and then returns the URL at the resulting position.

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

The max call ensures that the cursor never becomes negative, handling the case where the requested steps exceed the available backward history.

Moving Forward

The forward method increases the cursor by the requested number of steps, clamping it at the end of the list to avoid overflow, and returns the URL at the new cursor.

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

The min call guarantees that the cursor does not surpass the last stored URL, covering the scenario where the forward request is larger than the remaining forward history.

Edge Cases Handled

The implementation explicitly addresses boundary conditions for navigation:

• When visit is called while the cursor is not at the most recent entry, the forward segment is trimmed, preventing stale URLs from being reachable after a new navigation.
• In back, if the number of steps exceeds the distance to the first entry, the cursor is anchored at index 0, ensuring the method never attempts to access a negative index.
• In forward, if the steps exceed the distance to the last entry, the cursor is anchored at the final index (len(self.history) - 1), preventing out-of-range access.

These safeguards keep the internal state consistent regardless of the magnitude of the step arguments.

Performance Optimizations

The class relies on Python’s built-in list type, which provides amortized constant-time append operations. The slice used in visit creates a new list that contains only the relevant prefix; this operation is efficient because it copies at most the portion of the history that remains reachable after truncation. Cursor adjustments in back and forward are simple arithmetic and conditional clamps, both of which execute in constant time. Consequently, each public method performs a minimal amount of work proportional to the size of the operation’s input rather than the total length of the history.

Think of this code like a digital scrapbook for the websites you visit. First, it starts a list with your main homepage so it knows where you began. Every time you visit a new place, the scrapbook adds that new page to the end of the list, just like drawing a new picture on the next blank page. If you decide to go back or forward using the buttons, the scrapbook just moves a little marker to show which page you are looking at right now. When you go back, the marker slides toward the beginning of the list, and when you go forward, it slides toward the end. If you try to go further than the list allows, the marker stays safely at the very first or very last page so you do not get lost. If you visit a brand new site after going back, the scrapbook removes all the old pages that come after your current spot, making space for new adventures to be added in their place.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java					Go
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	everthis					JS
	fartem							Ruby
	FelixFan1122				C#
	fsq	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	martianoff						Scala
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
martianoff	Scala
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality