Problem statement

https://leetcode.com/problems/design-browser-history/

Solution

We can simulate our process with stack, where self.curr is current index we are on now and self.end is the index of the last avaliable element. We keep self.end to perform lazy deletions from stack. Instead of cut end of stack, we just say that it ends earlier.

Complexity

It is O(1) for time for all operations. It is O(n) for space.

Code

class BrowserHistory:
    def __init__(self, homepage):
        self.stack = [homepage]
        self.curr = 0
        self.end = 0

    def visit(self, url):
        if self.curr + 1 >= len(self.stack):
            self.stack += [""]
        self.stack[self.curr + 1] = url
        self.curr += 1
        self.end = self.curr

    def back(self, steps):
        self.curr = max(0, self.curr - steps)
        return self.stack[self.curr]
        
    def forward(self, steps):
        self.curr = min(self.end, self.curr + steps)
        return self.stack[self.curr]