Implement browser history: visit(url), back(steps), forward(steps). back/forward return the current URL after applying steps.
BrowserHistory("leetcode.com"), visit("google.com"), visit("facebook.com"), back(1)→"google.com", back(1)→"leetcode.com", forward(1)→"google.com"
Use a list with a current index pointer. On visit, clear forward history. On back/forward, clamp index.
- List history, int cur=0.
- visit: subList(cur+1, end).clear(); add url; cur=history.size()-1.
- back(k): cur = max(0, cur-k); return history[cur].
- forward(k): cur = min(history.size()-1, cur+k); return history[cur].
import java.util.*;
class BrowserHistory {
List<String> history = new ArrayList<>();
int cur = 0;
public BrowserHistory(String homepage) { history.add(homepage); }
public void visit(String url) {
while (history.size() > cur+1) history.remove(history.size()-1);
history.add(url); cur++;
}
public String back(int steps) { cur = Math.max(0, cur-steps); return history.get(cur); }
public String forward(int steps) { cur = Math.min(history.size()-1, cur+steps); return history.get(cur); }
}
- Time Complexity: visit: O(N) worst; back/forward: O(1)
- Space Complexity: O(N)