DSA problem
Design Browser History
You have a browser of one tab where you start on the homepage and you can visit another URL, get back in the history a number of steps, or move forward in the history. Implement the BrowserHistory class to model this behaviour with three operations.
BrowserHistory(homepage) initializes the object with the homepage as the only entry in history. visit(url) visits url from the current page — this clears all forward history. back(steps) moves steps back in history; if you can only go x < steps back, you stop at the earliest reachable page; returns the current URL. forward(steps) moves steps forward; similarly clamped to the most recent visited URL; returns the current URL.
The cleanest backing structure is a dynamic array that holds the entire history along with two pointers: currentIdx (the index of the page you are on) and len (the logical length, i.e., one past the most recent visit reachable by forward). A visit writes the new URL at currentIdx + 1 (resizing the array if needed) and sets both currentIdx and len to that new position, which effectively truncates forward history. back and forward shift currentIdx by the requested amount, clamped to [0, len - 1].
This gives O(1) per operation. An alternative is two stacks (back/forward), which has the same asymptotic complexity but is harder to clamp correctly. The array approach is the implementation most browsers actually use internally.
Examples
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]][null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]["BrowserHistory","visit","back","forward"]
[["a.com"],["b.com"],[1],[1]][null,null,"a.com","b.com"]["BrowserHistory","back","forward"]
[["start.com"],[5],[5]][null,"start.com","start.com"]Constraints
- 1 <= homepage.length <= 20
- 1 <= url.length <= 20
- 1 <= steps <= 100
- homepage and url consist of '.' or lower case English letters.
- At most 5000 calls will be made to visit, back, and forward.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.