I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1472. Design Browser History, the solution in this repository is mainly a data structure design solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design, stack.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are print, visit, back, forward.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 504 ms, faster than 25.92% of C++ online submissions for Design Browser History.
02//Memory Usage: 65 MB, less than 100.00% of C++ online submissions for Design Browser History.
03class BrowserHistory {
04public:
05 vector<string> fw, bw;
06 string cur;
07
08 BrowserHistory(string homepage) {
09 cur = homepage;
10 }
11
12 void print(){
13 cout << "fw: ";
14 for(int i = 0; i < fw.size(); i++){
15 cout << fw[i] << " ";
16 }
17 cout << endl;
18
19 cout << "bw: ";
20 for(int i = 0; i < bw.size(); i++){
21 cout << bw[i] << " ";
22 }
23 cout << endl;
24 cout << endl;
25 }
26
27 void visit(string url) {
28 fw.clear();
29 bw.push_back(cur);
30 cur = url;
31 // print();
32 }
33
34 string back(int steps) {
35 while(!bw.empty() && steps-- > 0){
36 fw.push_back(cur);
37 cur = bw.back(); bw.pop_back();
38 }
39
40 // print();
41 return cur;
42 }
43
44 string forward(int steps) {
45 while(!fw.empty() && steps-- > 0){
46 bw.push_back(cur);
47 cur = fw.back(); fw.pop_back();
48 }
49
50 // print();
51 return cur;
52 }
53};
54
55/**
56 * Your BrowserHistory object will be instantiated and called as such:
57 * BrowserHistory* obj = new BrowserHistory(homepage);
58 * obj->visit(url);
59 * string param_2 = obj->back(steps);
60 * string param_3 = obj->forward(steps);
61 */
62
63//two stacks
64//https://leetcode.com/problems/design-browser-history/discuss/674300/Two-Stacks-vs.-List
65//Runtime: 752 ms, faster than 5.01% of C++ online submissions for Design Browser History.
66//Memory Usage: 120 MB, less than 100.00% of C++ online submissions for Design Browser History.
67class BrowserHistory {
68public:
69 stack<string> fw, bw;
70 string cur;
71
72 BrowserHistory(string homepage) {
73 cur = homepage;
74 }
75
76 void visit(string url) {
77 fw = stack<string>(); //there is no stack::clear()!
78 bw.push(cur);
79 cur = url;
80 }
81
82 string back(int steps) {
83 while(!bw.empty() && steps-- > 0){
84 fw.push(cur);
85 cur = bw.top(); bw.pop();
86 }
87
88 return cur;
89 }
90
91 string forward(int steps) {
92 while(!fw.empty() && steps-- > 0){
93 bw.push(cur);
94 cur = fw.top(); fw.pop();
95 }
96
97 return cur;
98 }
99};
100
101/**
102 * Your BrowserHistory object will be instantiated and called as such:
103 * BrowserHistory* obj = new BrowserHistory(homepage);
104 * obj->visit(url);
105 * string param_2 = obj->back(steps);
106 * string param_3 = obj->forward(steps);
107 */
108
109//one vector holding backward and forward history
110//https://leetcode.com/problems/design-browser-history/discuss/674300/Two-Stacks-vs.-List
111//Runtime: 448 ms, faster than 39.59% of C++ online submissions for Design Browser History.
112//Memory Usage: 55 MB, less than 100.00% of C++ online submissions for Design Browser History.
113class BrowserHistory {
114public:
115 int cur = 0;
116 vector<string> hist;
117
118 BrowserHistory(string homepage) {
119 hist.push_back(homepage);
120 }
121
122 void visit(string url) {
123 /*
124 hist[0...cur] is backward history
125 hist[cur+1...] is forward history
126 */
127 //remove forward history
128 hist.resize(cur+1);
129 //store it into backward history
130 hist.push_back(url);
131 //cur now points to last element in hist
132 cur++;
133 }
134
135 string back(int steps) {
136 cur = max(0, cur-steps);
137 return hist[cur];
138 }
139
140 string forward(int steps) {
141 cur = min((int)hist.size()-1, cur+steps);
142 return hist[cur];
143 }
144};
145
146/**
147 * Your BrowserHistory object will be instantiated and called as such:
148 * BrowserHistory* obj = new BrowserHistory(homepage);
149 * obj->visit(url);
150 * string param_2 = obj->back(steps);
151 * string param_3 = obj->forward(steps);
152 */
153
154//speed up "visit"
155//Runtime: 272 ms, faster than 93.82% of C++ online submissions for Design Browser History.
156//Memory Usage: 55 MB, less than 100.00% of C++ online submissions for Design Browser History.
157class BrowserHistory {
158public:
159 int cur = 0;
160 vector<string> hist;
161
162 BrowserHistory(string homepage) {
163 hist.push_back(homepage);
164 }
165
166 void visit(string url) {
167 hist.resize(++cur);
168 hist.push_back(url);
169 }
170
171 string back(int steps) {
172 cur = max(0, cur-steps);
173 return hist[cur];
174 }
175
176 string forward(int steps) {
177 cur = min((int)hist.size()-1, cur+steps);
178 return hist[cur];
179 }
180};
181
182/**
183 * Your BrowserHistory object will be instantiated and called as such:
184 * BrowserHistory* obj = new BrowserHistory(homepage);
185 * obj->visit(url);
186 * string param_2 = obj->back(steps);
187 * string param_3 = obj->forward(steps);
188 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.