Coding Interview PatternsDesign Browser History
MediumCustom Data Structures

Design Browser History

Explanation & Solution

Practice Problem

Description

Design a browser history tracker that supports visiting URLs, going back, and going forward.

Implement a function that processes an array of operations and an array of arguments:

  • "BrowserHistory" — Initializes the browser with homepage as the current page.
  • "visit" — Visits url from the current page. This clears all forward history.
  • "back" — Moves steps back in history. Returns the current URL after moving (stops at the homepage if steps exceeds history).
  • "forward" — Moves steps forward in history. Returns the current URL after moving (stops at the most recent page if steps exceeds forward history).
Input:operations = ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"], args = [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
0
BrowserHistory
1
visit
2
visit
3
visit
4
back
5
back
6
forward
7
visit
8
forward
9
back
10
back
Output:[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
0
null
1
null
2
null
3
null
4
facebook.com
5
google.com
6
facebook.com
7
null
8
linkedin.com
9
google.com
10
leetcode.com

Explanation: Start at leetcode.com. Visit google, facebook, youtube. back(1)→facebook, back(1)→google, forward(1)→facebook. Visit linkedin (clears youtube). forward(2)→linkedin (no more forward). back(2)→google. back(7)→leetcode.

Constraints

  • 1 <= homepage.length, url.length <= 20
  • 1 <= steps <= 100
  • At most 5000 calls to visit, back, and forward

Approach

Custom Data Structures pattern

1. Use an Array with a Current Index

  • Store all visited URLs in an array history
  • Track curr — the index of the current page
  • Pages before curr are backward history; pages after are forward history

2. Implement Visit

  • Truncate the array to history.slice(0, curr + 1) — this clears forward history
  • Push the new URL to the end
  • Increment curr

3. Implement Back

  • Decrease curr by steps, clamped to 0 using Math.max
  • Return history[curr]

4. Implement Forward

  • Increase curr by steps, clamped to history.length - 1 using Math.min
  • Return history[curr]

5. Why Truncate on Visit?

  • Visiting a new page from a back-navigated position invalidates future history
  • Slicing discards all pages after curr before appending the new URL

Key Insight

  • A simple array + integer pointer models the browser stack perfectly
  • Forward history is just the suffix of the array beyond curr
  • Visiting clears it; back/forward shift the pointer
Time
O(n) for visit (due to slice), O(1) for back/forward
Space
O(n)

Solution Code

Previous
LRU Cache
Next
Design Hit Counter