Problem overview
A browser tab starts on a homepage. The class BrowserHistory lets it visit(_:) a new page, go back(_:) some number of pages, or go forward(_:) some number of pages. back and forward return the url of the page where the tab ends up, and they stop at the ends of the history: asking for more steps than exist goes as far as possible. Visiting a new page erases every page ahead of the current one, as a real browser does.
Take a tab that starts on "home.com". After visit("a.com") and visit("b.com"), back(5) can only go back two pages and returns "home.com". Then forward(1) returns "a.com" and forward(9) goes as far as it can, to "b.com". The statement wants every call to take O(1) time, however large steps is.
Approach: one array and two indexes
The natural first design uses two stacks: pages behind the current one and pages ahead. back(steps) pops pages from one stack and pushes them on the other, one at a time. That works, but a call with steps = 100000 takes O(steps) time.
A single array removes the walking. The class keeps the pages in the order they were visited and two indexes:
current: the index of the page the tab is on;last: the index of the last pageforwardmay reach.
back and forward only change current, by any number of steps at once. Going back is max(0, current - steps), which stops at the homepage. Going forward is min(last, current + steps), which stops at the last page of the history.
Visiting a page must erase the pages ahead, and the trick is not to erase anything. The new page goes at index current + 1, and last is set to that index. Pages after last may still sit in the array, but forward never goes past last, and later visits write over them. Erasing is a single assignment.
Here is that in action, starting from "home.com". After the visits to a, b and c, the array is ["home.com", "a.com", "b.com", "c.com"] with current 3. back(2) moves current to 1 and returns "a.com". Now visit("d.com") writes over index 2, giving ["home.com", "a.com", "d.com", "c.com"] with current and last both 2. The old "c.com" is still in the array, and no call can reach it.
Step by step
- Declare
historyas avarof type[String]. The initializer fills it. - Declare
currentas avarset to 0: the tab starts on the homepage. - Declare
lastas avarset to 0, since at first the homepage is the last page too. - In
init, sethistoryto an array holding justhomepage. Every stored property must have a value when the initializer ends, andcurrentandlastalready do. - In
visit, add 1 tocurrent: the new page goes right after the current one. - If
current < history.count, an erased page sits at that index: sethistory[current]tourl. - Otherwise the array ends at the current page: append
url. - Set
lasttocurrent. This one line erases the forward history. - In
back, setcurrenttomax(0, current - steps). - Return
history[current]. - In
forward, setcurrenttomin(last, current + steps). The cap islast, not the end of the array. - Return
history[current]again.
The solution in Swift
class BrowserHistory {
var history: [String]
var current = 0
var last = 0
init(_ homepage: String) {
history = [homepage]
}
func visit(_ url: String) {
current += 1
if current < history.count {
history[current] = url
} else {
history.append(url)
}
last = current
}
func back(_ steps: Int) -> String {
current = max(0, current - steps)
return history[current]
}
func forward(_ steps: Int) -> String {
current = min(last, current + steps)
return history[current]
}
}
The Swift details worth a closer look:
- Setting a property in
init.historyhas no default, soinitmust give it one.currentandlasthave defaults of 0 and need nothing. Insideinit,history = [homepage]is enough, and writingself.is not needed because the names don't clash with a parameter. - The global
maxandmin.max(0, current - steps)picks the larger of twoIntvalues. The class has no methods with these names, so the calls go to Swift's global functions. - Methods that change state and return a value.
backandforwardassign tocurrentand then return a page. BecauseBrowserHistoryis a class, nothing needs to be markedmutating. - Index versus count.
history.countis the number of stored pages, including erased ones.lastis what says which pages are real. - Array bounds. Reading
history[current]outside the array stops the program at run time. Themaxandminkeepcurrentbetween 0 andlast, so the index is always inside.
Complexity
Time. Every method takes O(1): visit writes or appends one element (an append is amortized O(1)), and back and forward are one subtraction or addition with a bound, whatever steps is.
Space. O(n) for n visits. The array never shrinks, but it never holds more pages than the longest history the tab has had.
Edge cases and common mistakes
- Going back from the homepage.
back(1)on a fresh tab returns the homepage. Withoutmax(0, ...),currentwould become -1 and the next read would crash. - Too many steps back.
back(7)goes only as far as the homepage. The same holds forback(100000), with no loop. - Going forward with nothing ahead. After a visit,
forward(2)stays on the page just visited, becauselastequalscurrent. - Capping
forwardat the array's end. That would reach erased pages. With home, a, b and c visited,back(2), thenvisit("d.com"), the array still ends with "c.com", butforward(1)returns "d.com" and stays there. - Forgetting to set
lastinvisit. The forward history would not be erased, andforwardcould return a page from the old branch. - Always appending in
visit. Appending after abackwould put the new page at the wrong index, after the erased pages, andcurrentwould no longer point to it. The page is written atcurrent + 1. - Removing the erased pages from the array. It is correct but costs time proportional to the number of pages removed; overwriting costs
O(1).
Testing
- Start on
"home.dev", visit "a.dev", "b.dev" and "c.dev". Thenback(1),back(1),forward(1)return "b.dev", "a.dev", "b.dev". Aftervisit("d.dev"),forward(2),back(2)andback(7)return "d.dev", "a.dev", "home.dev". - Start on
"home.com":back(1)returns "home.com". After visits to "a.com" and "b.com",back(5),forward(1),forward(9)return "home.com", "a.com", "b.com". - Start on
"home.com", visit "a.com", "b.com", "c.com", thenback(2)returns "a.com". Aftervisit("d.com"),forward(1),back(1)andforward(2)return "d.com", "a.com", "d.com".
