Python 3 | Three Methods | Explanations
Approach \#1. Brutal Force\n- Straight forward solution, actual do snap very time snap is called\n- This is quick to access, but take lots of extra space and it
### Approach \\#1. Brutal Force\n- Straight forward solution, actual do snap very time `snap` is called\n- This is quick to access, but take lots of extra space and it takes time to take snap shot, as we need to make a copy\n```\nclass SnapshotArray:\n    def __init__(self, length: int):\n        self.cache = []\n        self.d = dict()\n        self.i = 0\n\n    def set(self, index: int, val: int) -> None:\n        self.d[index] = val\n\n    def snap(self) -> int:\n        self.cache.append(dict(self.d))\n        self.i += 1\n        return self.i-1\n\n    def get(self, index: int, snap_id: int) -> int:\n        snap = self.cache[snap_id]\n        return snap[index] if index in snap else 0\n```\n\n### Approach \\#2. `defaultdict` + `OrderedDict` + Binary Search\n- Take individual snap shot when `set` is called, increment snap id (`self.i`), when `snap` is called\n- This is fast to `set` & `snap` but relatively slow when you do an get\n\t- even if it\'s binary search, make `keys` indexable take time \n- It save space too\n```\nclass SnapshotArray:\n    def __init__(self, length: int):\n        self.cache = collections.defaultdict(lambda : collections.OrderedDict())\n        self.i = 0\n\n    def set(self, index: int, val: int) -> None:\n        self.cache[index][self.i] = val\n\n    def snap(self) -> int:\n        self.i += 1\n        return self.i-1\n        \n    @lru_cache(maxsize=None)    \n    def get(self, index: int, snap_id: int) -> int:\n        if index not in self.cache: return 0\n        else:\n            idx_cache = self.cache[index]\n            if snap_id in idx_cache: return idx_cache[snap_id]\n            else:\n                keys = list(idx_cache.keys()) \n                i = bisect.bisect(keys, snap_id)\n                if snap_id > keys[-1]: return idx_cache[keys[-1]]\n                elif i == 0: return 0\n                else: return idx_cache[keys[i-1]]\n```\n### Approach \\#3. List of list + Binary Search\n- A little combination of two above\n- Space used in greater than approach \\#2 and less than approach \\#1\n- Fast to `set` and `snap`, `get` speed should be faster than apporach \\#2 but slower than approach \\#1\n```\nclass SnapshotArray(object):\n    def __init__(self, n):\n        self.cache = [[[-1, 0]] for _ in range(n)]\n        self.i = 0\n\n    def set(self, index, val):\n        self.cache[index].append([self.i, val])\n\n    def snap(self):\n        self.i += 1\n        return self.i - 1\n\n    @lru_cache(maxsize=None)\n    def get(self, index, snap_id):\n        i = bisect.bisect(self.cache[index], [snap_id + 1]) - 1\n        return self.cache[index][i][1]    \n```
['Binary Search', 'Python', 'Python3']