Problem overview
A browser tab starts on a homepage. The struct BrowserHistory has four methods: BrowserHistory::new(homepage) starts the tab, visit(url) goes to a new page, back(steps) goes back that many pages, and forward(steps) goes forward. Both back and forward return the url of the page the tab ends on, and both stop at the end of the history if steps is too large. Visiting a new page erases every page ahead of the current one, the way a real browser does.
In the third example, the tab starts on home.com and visits a.com, b.com and c.com. After back(2) the tab is on a.com, with b.com and c.com ahead. visit("d.com") erases both, so forward(1) stays on d.com, back(1) returns a.com, and forward(2) can only reach d.com.
The statement asks for O(1) time per call, whatever steps is.
Approach: one list and two indexes
The familiar design uses two stacks: one for the pages behind and one for the pages ahead. A back pops pages from one and pushes them on the other, one page at a time, so back(steps) and forward(steps) take O(steps). With steps up to 100,000 that adds up.
A single vector of pages in visit order does better, together with two indexes. current is the index of the page the tab is on. last is the index of the last page that forward may reach. Then back and forward are arithmetic on current: subtract and stop at 0, or add and stop at last. There is no loop, so both take O(1).
The trick is how a visit erases the forward pages without deleting anything. The new page is written at current + 1, replacing whatever was there, and last is set to current. Pages beyond last may still sit in the vector, but forward never goes past last, and later visits overwrite them. Overwriting one slot is O(1); removing the pages would not be.
The third example, with the vector and both indexes after each step:
new: history=["home.com"] current=0 last=0
3 visits: history=["home.com", "a.com", "b.com", "c.com"] current=3 last=3
back(2): returns a.com, current=1 last=3
visit(d.com): history=["home.com", "a.com", "d.com", "c.com"] current=2 last=2
After the last visit, c.com is still in the vector at index 3. Because last is 2, forward never reaches it.
Step by step
- Declare
history, aVec<String>with the pages in order. - Declare
current, ausizeindex into it: the page the tab is on. - Declare
last, also ausize: the last indexforwardcan reach. - In
new, start the history asvec![homepage]withcurrentandlastat 0. - In
visit, movecurrentone page ahead: the new page goes right after the current one. - If that index is inside the vector, overwrite the erased page stored there with
url. - Otherwise push
urlonto the vector, since the history reaches further than it ever did. - Set
lasttocurrent. This single assignment erases the forward history. - In
back, subtractsteps as usizefromcurrentwithsaturating_sub, so the result stops at 0. - Return a clone of the page at
current. - In
forward, setcurrentto the smaller oflastandcurrent + steps as usize. - Return a clone of the page at
currentagain.
The solution in Rust
struct BrowserHistory {
history: Vec<String>,
current: usize,
last: usize,
}
impl BrowserHistory {
fn new(homepage: String) -> BrowserHistory {
BrowserHistory { history: vec![homepage], current: 0, last: 0 }
}
fn visit(&mut self, url: String) {
self.current += 1;
if self.current < self.history.len() {
self.history[self.current] = url;
} else {
self.history.push(url);
}
self.last = self.current;
}
fn back(&mut self, steps: i32) -> String {
self.current = self.current.saturating_sub(steps as usize);
self.history[self.current].clone()
}
fn forward(&mut self, steps: i32) -> String {
self.current = self.last.min(self.current + steps as usize);
self.history[self.current].clone()
}
}
Using it on the first example, starting from the homepage and visiting google.com, facebook.com and youtube.com, the calls back(1), back(1) and forward(1) return facebook.com, google.com and facebook.com. After visit("linkedin.com"), forward(2) returns linkedin.com, back(2) returns google.com, and back(7) returns the homepage.
The Rust details worth a closer look:
saturating_sub. Ausizecannot be negative. In the optimized build the lessons use,0 - 1on ausizewraps to a huge number; in a debug build it panics.saturating_substops at 0 instead:0usize.saturating_sub(5)is 0. That is the "stay on the homepage" rule.steps as usize. The parameter is ani32but the index is ausize, and Rust does not convert between integer types on its own. The constraints keepstepsat 1 or more, so the cast is safe. A negativestepswould turn into a huge number.a.min(b). Integers have aminmethod, soself.last.min(self.current + steps as usize)is the smaller of the two. It keepscurrentfrom passinglast.- Overwriting and pushing.
self.history[self.current] = urlmoves the new string into an existing slot and drops the old one.pushappends. Indexing out of bounds would panic, which is why the code checksself.current < self.history.len()first. .clone(). The vector must keep its own strings, so the methods return a copy. Returningself.history[self.current]directly would try to move aStringout of a vector, which Rust rejects.&mut selfeverywhere.backandforwardlook like readers, but they changecurrent.
Complexity
Time. Every method does a constant number of operations: an index update, one comparison, one write or push, and at most one clone of a string of up to 20 characters. visit, back and forward are O(1), independent of steps (a push is O(1) amortized).
Space. O(n), where n is the number of pages the history held at its longest. Erased pages stay in the vector until a later visit overwrites them, but the vector never holds more pages than the longest history reached.
Edge cases and common mistakes
- Going back past the homepage. From the homepage,
back(1)returns the homepage. From a history of two pages,back(100000)also returns the first page. - Going forward past the end. With nothing ahead,
forward(9)stays on the current page. The limit islast, not the end of the vector. - Capping
forwardat the vector's length. In the third example,c.comis still in the vector aftervisit("d.com"). Capping at the length would letforward(2)reachc.cominstead of stopping atd.com. - Forgetting to update
lastinvisit. The erased pages would become reachable again. - Always pushing in
visit. After aback, the new page would land at the end of the vector whilecurrentmoves only one step. The history would be out of sync. - Visiting after going back. From a history of
home.comanda.com,back(1)and thenvisit("z.com")leaves the history ashome.com,z.com. The slot ofa.comwas overwritten. - Using two stacks. It works, but
back(100000)then costs 100,000 moves.
Testing
- Homepage
home.com, thenback(1),visit("a.com"),visit("b.com"),back(5),forward(1),forward(9)giveshome.com,home.com,a.com,b.com. - Homepage
home.com, visits toa.com,b.comandc.com, thenback(2),visit("d.com"),forward(1),back(1),forward(2)givesa.com,d.com,a.com,d.com.
