Design Browser History LeetCode 1472

LeetCode 1472 asks you to implement a BrowserHistory class that simulates the way a real web browser manages navigation. You start at a given homepage and can visit new URLs, move back a number of steps, and move forward a number of steps.

The visit(url) operation is where things get interesting: every time you visit a new page, all forward history is erased. If you went back five pages and then visited a new URL, you can no longer go forward to any of those five pages. This truncation behavior is what separates a correct implementation from a naive one.

The back(steps) and forward(steps) operations move you as many steps as requested, but clamp at the available boundaries — you can never go past the beginning or the end of your current history chain.

The cleanest solution uses a plain list (array) and two integer markers: current (the index of the page you are on right now) and end (the index one past the last valid forward page). When you call visit, you write the new URL at position current + 1, bump current to current + 1, and set end to current + 1. Anything that was at higher indices is now silently ignored — that is your truncation for free.

Back and forward are trivially O(1): back(steps) sets current = max(0, current - steps), while forward(steps) sets current = min(end - 1, current + steps). No deletion, no reallocation, no shifting. You just move a number.

The array does grow over time as you visit pages — O(n) space in total — but each individual operation is O(1). This is both the simplest and the fastest practical approach, and it is the one you should reach for first in an interview.

When visit(url) is called, you do not append to the end of the array — you write at index current + 1. This is critical. If you are three pages back in history and you visit a new URL, you want to overwrite from that position forward, not extend the real end of the underlying list.

After writing, update current = current + 1 and set end = current + 1 (or equivalently end = current after the increment). From this point on, any index >= end is treated as nonexistent even if the array physically holds old values there. The "truncation" is purely logical — nothing is actually deleted.

If you are using Python and the list is not long enough to have an element at current + 1, you can either extend it with a placeholder or maintain end carefully to know you need to append. A common clean pattern: if current + 1 < len(history): history[current + 1] = url; else: history.append(url). Then current += 1; end = current + 1.

Back and forward are the simplest methods once the array-and-pointer structure is in place. For back(steps), compute new_pos = current - steps and clamp: current = max(0, new_pos). Return history[current]. For forward(steps), compute new_pos = current + steps and clamp: current = min(end - 1, new_pos). Return history[current].

Both operations are O(1) — no loops, no traversal. The clamping logic ensures you never read out of bounds even if the caller passes an absurdly large steps value. This is a requirement of the problem: back and forward must return the actual URL you land on, which may be fewer than steps pages away from where you started.

It is worth noting that neither back nor forward modifies the end pointer. Only visit changes end. This means you can go back and then forward again along the same history chain as long as no new visit has happened in between.

A doubly linked list models the browser history chain more literally: each node holds a URL plus prev and next pointers, and a current pointer walks the chain. visit(url) creates a new node, links it after current, severs the forward chain by setting current.next.prev = None (and current.next = new_node), and advances current to the new node.

Back and forward traverse the list link by link, moving the current pointer until steps are exhausted or a boundary is hit. Because traversal is proportional to the number of steps, each operation is O(steps) in the worst case — not O(1) like the array version. For the problem constraints this is acceptable, but the array approach is strictly faster.

The linked list shines when you want strict memory efficiency for sparse navigation patterns — if you only ever visit a handful of URLs but jump many steps at once, no wasted array slots. It also avoids the occasional need to extend the array. In practice, however, the array approach is preferred in interviews for its simplicity and constant-time operations.

In Python, the array version fits in about 15 lines total. The constructor initializes self.history = [homepage], self.current = 0, self.end = 1. The visit method handles the extend-or-overwrite pattern. Back and forward are single-line clamp-and-assign operations that return history[self.current].

In Java, the same structure uses a String[] array pre-allocated to the maximum possible size (5001 entries given the constraints), avoiding the extend step entirely. current and end are int fields. All three methods are single-pass O(1). The linked list version in Java requires a private inner Node class with String url, Node prev, next fields, and the traversal loops replace the clamp arithmetic.

For the array version, remember that Python list indexing and Java array access behave differently on out-of-bounds. Pre-allocating in Java eliminates the branch. In either language, both approaches pass the problem constraints comfortably within time and memory limits.

Design Browser History belongs to the data-structure-design family on LeetCode — problems where you implement a class with multiple operations that must work together efficiently. The key skill is choosing the right underlying structure for the access patterns described.

LRU Cache (LeetCode 146) is the most famous member of this family: it requires O(1) get and put, forcing you to combine a hash map with a doubly linked list. Design Circular Queue (LeetCode 622) uses a fixed-size array with head and tail pointers — a direct relative of the array-and-pointer pattern used here. Design Hit Counter (LeetCode 362) involves sliding-window time-based queries, a different pattern but the same design-class mindset.

If you are building toward a FAANG interview, practice this entire family: Browser History, LRU Cache, Circular Queue, Hit Counter, and Min Stack (LeetCode 155). They share the theme of wrapping simple data structures with clever pointer arithmetic to hit time complexity targets.