Python | Two Solutions
Approach\nFirst approach (at the bottom of the code) was to directly simulate the process using caching. We keep track of the last day a room was visited in las
# Approach\nFirst approach (at the bottom of the code) was to directly simulate the process using caching. We keep track of the last day a room was visited in ```last_day``` and the number of times a room has been visited in ```visits```. The calculations performed coalesce into the dynamic programming solution at the top.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def firstDayBeenInAllRooms2(self, next_visit: List[int]) -> int:\n        p = 10**9 + 7\n        n = len(next_visit)\n        dp = [0]*n\n\n        for i in range(1,n):\n            dp[i] = (2 * dp[i-1] - dp[next_visit[i-1]] + 2) % p\n\n        return dp[-1]\n\n    def firstDayBeenInAllRooms(self, next_visit: List[int]) -> int:\n        p = 10**9 + 7\n        n = len (next_visit)\n        not_visited = set(range(n))\n\n        visits = [0] * n\n        last_day = [float(\'-inf\')] * n\n\n        def simulate (room, day):\n            not_visited.discard(room)\n            while not_visited:\n                visits[room] += 1\n                last_day[room] = day\n                if visits[room] & 1:\n                    # This room has been visited an odd number of times.\n                    day = (2*day - last_day[next_visit[room]] + 1) % p\n\n                # This room has been visited an even number of times.\n                day += 1\n                room = (room + 1) % n\n                not_visited.discard(room)\n\n            return day\n\n        return simulate (0, 0) % p\n```
['Python3']