LC-1472 Medium LeetCode

1472. Design Browser History

Array Linked List Stack Design Doubly-Linked List Data Stream

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 78% Topics: Array, Linked List, Stack, Design, Doubly-Linked List, Data Stream

Reading material

Arrays & Hashing 12 min Linked Lists 14 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  ctor  : O(1)
#        visit : O(n)
#        back  : O(1)
#        foward: O(1)
# Space: O(n)

class BrowserHistory(object):

    def __init__(self, homepage):
        """
        :type homepage: str
        """
        self.__history = [homepage]
        self.__curr = 0        

    def visit(self, url):
        """
        :type url: str
        :rtype: None
        """
        while len(self.__history) > self.__curr+1:
            self.__history.pop()
        self.__history.append(url)
        self.__curr += 1

    def back(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        self.__curr = max(self.__curr-steps, 0)
        return self.__history[self.__curr]

    def forward(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        self.__curr = min(self.__curr+steps, len(self.__history)-1)
        return self.__history[self.__curr]

Solution from kamyu104/LeetCode-Solutions · MIT