[Python] HashMap & Binary Search - Clean & Concise
Idea\n- We map index with (snapId, val), let name it map.\n- For get(index, snapId):\n\t- Get versions from the map based on index, arr = map[index].\n\t- We bi
**Idea**\n- We map `index` with `(snapId, val)`, let name it `map`.\n- For `get(index, snapId)`:\n\t- Get versions from the map based on `index`, `arr = map[index]`.\n\t- We binary search on `arr` to find the version, which has largest snapId <= `snapId`.\n\t- For example: \n\t\t- set(index=1, val=9), snapId = 0\n\t\t- snap(), snapId = 1\n\t\t- snap(), snapId = 2\n\t\t- get(index=1, snapId=2)\n```python\nclass SnapshotArray:\n    def __init__(self, length: int):\n        self.map = defaultdict(list)\n        self.snapId = 0\n\n    def set(self, index: int, val: int) -> None:\n        if self.map[index] and self.map[index][-1][0] == self.snapId:\n            self.map[index][-1][1] = val\n            return\n        self.map[index].append([self.snapId, val])\n\n    def snap(self) -> int:\n        self.snapId += 1\n        return self.snapId - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n        arr = self.map[index]\n        left, right, ans = 0, len(arr) - 1, -1\n        while left <= right:\n            mid = (left + right) // 2\n            if arr[mid][0] <= snap_id:\n                ans = mid\n                left = mid + 1\n            else:\n                right = mid - 1\n        if ans == -1: return 0\n        return arr[ans][1]\n```\nComplexity:\n- Time: \n\t- Constructor, set, snap: `O(1)`\n\t- get: `O(logN)`\n- Space: `O(N)`
[]