Problem overview
A browser tab starts on a homepage. From any page it can visit a new page, go back some number of pages, or go forward again. Visiting a new page erases the pages that were ahead, as a real browser does.
The class BrowserHistory has a constructor BrowserHistory(homepage) and three methods. visit(url) moves to url and erases every page ahead of the current one. back(steps) goes back steps pages, or as far as it can, to the homepage, and returns the page it ends on. forward(steps) goes forward steps pages, or as far as it can, and returns the page it ends on.
In the first example, the history is start.com, news.com, shop.com, video.com. Then back(1), back(1) and forward(1) return shop.com, news.com and shop.com. Visiting jobs.com erases video.com, the page that was ahead, so forward(2) cannot move and returns jobs.com. back(2) returns news.com and back(7), which can only go one more page, returns start.com. The six results:
shop.com news.com shop.com jobs.com news.com start.com
Approach: one list, a current index and a last index
A natural design uses two stacks, one for the pages behind and one for the pages ahead. back pops from one and pushes onto the other, one page at a time, so back(steps) costs O(steps). With steps up to 100,000, that is slow. On a history of 50,000 pages, 2,000 round trips of back(50000) and forward(50000) took 789 ms with two stacks, and 0.21 ms with the design below, where both versions ended on the same page.
The faster design keeps all the pages in one array, this.history, in visit order, plus two indexes:
this.current: the index of the page the tab is on;this.last: the index of the last page thatforwardmay reach.
Now back and forward only change this.current, by any number of steps at once, with one subtraction or addition and a clamp at 0 or at this.last. Each call costs O(1), whatever steps is.
The trick is visit. Erasing the forward pages one by one would be slow, and it is not needed. A visit puts the new page right after the current one and sets this.last to the new page's index. Pages after this.last may still sit in the array, but forward never goes past this.last, and later visits overwrite them. One line, this.last = this.current, erases the entire forward history.
Here is the state as the third example runs (home.com, then visits to a, b, c, then back(2), then a visit to d):
start: ["home.com"] current 0 last 0
visit a, b, c: ["home.com","a.com","b.com","c.com"] current 3 last 3
back(2) => a.com: current 1 last 3
visit d: ["home.com","a.com","d.com","c.com"] current 2 last 2
forward(1) => d.com: current 2 last 2
After the visit, c.com is still in the array at index 3, but last is 2, so forward can never reach it. The following back(100) returns home.com (current 0), and forward(100) returns d.com (current 2, capped by last).
Step by step
- Constructor: set
this.historyto an array holding justhomepage, at index 0. - Set
this.currentto 0: the tab starts on the homepage. - Set
this.lastto 0: for now the homepage is also the last page forward can reach. - visit: move
this.currentone page ahead with++. The new page takes the next index. - If
this.current < this.history.length, an erased page still sits at that index, so setthis.history[this.current]tourl. Overwriting takesO(1); deleting pages would not. - Otherwise, in an
else, the array ends at the current page, sopushurlontothis.history. - After the
if/else, setthis.lasttothis.current. This is the line that erases the forward history. - back: set
this.currenttoMath.max(0, this.current - steps). Index 0 is the homepage, the furthest back. - Return
this.history[this.current]. - forward: set
this.currenttoMath.min(this.last, this.current + steps). The cap isthis.last, not the end of the array, because pages afterthis.lastwere erased. - Return
this.history[this.current], the same line as at the end ofback.
The solution in JavaScript
class BrowserHistory {
constructor(homepage) {
this.history = [homepage];
this.current = 0;
this.last = 0;
}
visit(url) {
this.current++;
if (this.current < this.history.length) {
this.history[this.current] = url;
} else {
this.history.push(url);
}
this.last = this.current;
}
back(steps) {
this.current = Math.max(0, this.current - steps);
return this.history[this.current];
}
forward(steps) {
this.current = Math.min(this.last, this.current + steps);
return this.history[this.current];
}
}
JavaScript details:
this.current++as a statement adds 1 to the property. It is the same asthis.current += 1.- Assigning past the end. JavaScript allows
arr[arr.length] = x, which appends, but the lesson uses an explicitif/elsewithpushfor clarity. Theelsebranch only runs whenthis.currentequalsthis.history.length. Math.maxandMath.minclamp a number into a range in one expression. Noifis needed.- Constructor arguments. The constructor takes
homepageand the class does not keep it as a separate field; it is the first element ofthis.history.
Complexity
Time: visit, back and forward are all O(1). Each does a few comparisons and assignments and at most one array push. steps never appears in the cost.
Space: O(n), where n is the largest number of pages the history ever reached at once. The array only grows when a visit goes beyond its current length; otherwise it overwrites.
Edge cases and common mistakes
- Going back too far. Without the
Math.max(0, ...)clamp,back(5)from index 2 would setcurrentto -3, andthis.history[-3]isundefined. In the second exampleback(1)at the homepage stays onhome.com, andback(5)fromb.comgoes back two pages, tohome.com. - Capping
forwardat the array length. The cap must bethis.last. In the third example,c.comis still in the array after visitingd.com, and a cap at the end would letforward(2)reach it. The correct result isd.com. - Forgetting to update
this.lastinvisit. Then forward would still reach the erased pages. Updating it on every visit, not only when the array grows, is essential. - Visiting in the middle. The new page overwrites the next slot, so the array can hold stale pages after
this.last. That is harmless, since nothing reads pastthis.last. - Forward with nothing ahead. When
this.currentequalsthis.last,Math.minreturnsthis.lastand the tab stays put:forward(2)after the last visit in the first example returnsjobs.com.
Testing
Outputs of the solution above:
- Example 1 returns
shop.com news.com shop.com jobs.com news.com start.com. - Example 2 (
BrowserHistory("home.com"),back(1), visits to a and b,back(5),forward(1),forward(9)) returnshome.com home.com a.com b.com. - Example 3 returns
a.com d.com a.com d.com.
