Problem overview
A browser tab starts on a homepage. From its current page it can visit a new page, go back some number of pages, or go forward again. Visiting a new page erases the pages you could have gone forward to. The class is BrowserHistory:
constructor(homepage)starts the tab onhomepage.visit(url)goes tourland erases every page ahead of the current one.back(steps)goes backstepspages, or as far as the homepage if fewer are behind. It returns the url it ends on.forward(steps)goes forwardstepspages, or as far as it can. It returns the url it ends on.
Take a tab that starts on home.com and visits a.com, b.com and c.com. Then back(2) returns a.com, with b.com and c.com ahead. After visit("d.com"), both of those pages are erased, so the history is home.com, a.com, d.com. The calls forward(1), back(1) and forward(2) then return d.com, a.com and d.com.
Approach: one list, a current index and a last index
Two stacks work: one for the pages behind, one for the pages ahead. back(steps) pops steps pages from one stack and pushes them onto the other, one page at a time, so it takes O(steps). The statement asks for O(1) per call, whatever steps is.
The better idea keeps every page in one array in the order visited, and two indexes:
current: the index of the page the tab is on.last: the index of the last page thatforwardcan reach.
Then back and forward only change current, by any number of steps at once: a subtraction clamped at 0, or an addition clamped at last. A visit writes the new page right after current and sets last to the same index. That one assignment is the erasing: pages after last may still sit in the array, but forward never goes past last, and later visits write over them. In the example above, after visit("d.com") the array is ["home.com", "a.com", "d.com", "c.com"] with current and last both at 2, so c.com is still stored but unreachable.
Step by step
- Declare
historyas astring[], set to an empty array. - Declare
currentas anumber, set to 0: the tab starts on the homepage. - Declare
lastas anumber, set to 0: at the start the homepage is also the last reachable page. - In the constructor, push
homepageontothis.history, at index 0. visit, move ahead: dothis.current++. The new page goes right after the current one.- Overwrite an erased page: if
this.current < this.history.length, an old page sits at that index and is erased by this visit. Setthis.history[this.current]tourl. - Otherwise the array ends at the current page, so push
url. - Cut the future: after the
if/else, setthis.last = this.current. back: setthis.currenttoMath.max(0, this.current - steps), so it never goes below the homepage.- Return
this.history[this.current]. forward: setthis.currenttoMath.min(this.last, this.current + steps). The cap islast, not the end of the array, because pages afterlastwere erased.- Return
this.history[this.current].
The solution in TypeScript
class BrowserHistory {
history: string[] = [];
current: number = 0;
last: number = 0;
constructor(homepage: string) {
this.history.push(homepage);
}
visit(url: string): void {
this.current++;
if (this.current < this.history.length) {
this.history[this.current] = url;
} else {
this.history.push(url);
}
this.last = this.current;
}
back(steps: number): string {
this.current = Math.max(0, this.current - steps);
return this.history[this.current];
}
forward(steps: number): string {
this.current = Math.min(this.last, this.current + steps);
return this.history[this.current];
}
}Details:
- The field initializers (
= [],= 0) run before the constructor body, sothis.history.push(homepage)in the constructor finds an array waiting. this.current++changes the field in place. It is a statement of its own here, so whether it is written before or after the field doesn't matter.- Assigning to an index inside the array (
this.history[this.current] = url) replaces a page;pushadds one at the end. The code never removes pages, which is whyvisitstaysO(1). Math.maxandMath.minclamp the index in one expression, without anyif.
A longer run
Start on home.org, then visit a.org, b.org and c.org. The calls back(1), back(1) and forward(1) return b.org, a.org and b.org. Now visit("d.org") writes d.org over c.org, so the array is ["home.org", "a.org", "b.org", "d.org"] with current and last both equal to 3. The next calls behave like this:
forward(2)returnsd.org: nothing is ahead, so the tab stays.back(2)returnsa.org.back(7)returnshome.org: only one page is left behind, so it stops at the homepage.
Complexity
Every method is O(1) in time, whatever steps is: an index change, a comparison, and either an assignment or a push. Space is O(n) for the n pages stored. The array never shrinks, but it never holds more pages than the longest history the tab ever had.
Edge cases and common mistakes
- Going back past the homepage. On a tab that has only
home.com,back(1)returnshome.com. After visitinga.comandb.com,back(5)returnshome.com, because only two pages are behind. - Going forward past the end. From
home.comin that same tab,forward(1)returnsa.comandforward(9)returnsb.com, the last page. - Capping
forwardat the end of the array. The array can hold erased pages afterlast. In the example, the array's end isc.combutforwardmust stop atd.com. - Forgetting to update
lastinvisit. Then erased pages become reachable again. - Using
spliceto remove the erased pages. It works, but costs time proportional to the number of pages removed. - Visiting from the middle. From the second page of a long history,
visitoverwrites the third page andlastbecomes 2, wherever the old end was.
