Design browser history

Implement BrowserHistory(homepage) with visit(url), back(steps) and forward(steps). Visiting a page clears all forward history. back and forward move at most as far as the history allows and return the current page.

Before you code

Going back undoes visits in reverse order, so the pages behind you form a stack. Pages you went back from form a second stack, which a new visit throws away. That is exactly how undo and redo work in an editor.

Hints

1. Two stacks: back_stack holds the pages before the current one, fwd_stack the pages after it.
2. back(steps): move pages from back_stack to fwd_stack one at a time, as long as back_stack is non-empty.
3. visit(url): push the current page onto back_stack and clear fwd_stack.
4. Alternative with O(1) back and forward: an array of pages, a cursor and a last index. visit overwrites the slot after the cursor and sets last to it.

Production & complexity notes

When solving Design browser history on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stacks and the LIFO rule to reinforce the underlying pattern.

What it practices

The undo/redo pattern of two stacks, from Stacks and the LIFO rule.