👏🏻 Python |  Brute Force + Improved Code 公瑾™
Brute Force | \tMemory Limit Exceeded\n\nMemory usage needs to be more efficient. In this code snippet, too many unused 0 element were stored in the dictionary 
#### Brute Force | \tMemory Limit Exceeded\n\nMemory usage needs to be more efficient. In this code snippet, too many unused `0` element were stored in the dictionary value. Instead, only store used index and value. A nested dictionary does the trick\n\n```python\nclass SnapshotArray(object):\n\n    def __init__(self, length):\n        self.length = length\n        self.arr = [0] * self.length\n        self.snap_id = -1\n        self.dic = {}\n        \n\n    def set(self, index, val):\n        if index >= 0 and index < len(self.arr):\n            self.arr[index] = val\n\n    def snap(self):\n        self.snap_id += 1\n        self.dic[self.snap_id] = self.arr[:]\n        return self.snap_id\n        \n\n    def get(self, index, snap_id):\n        if snap_id in self.dic:\n            return self.dic[snap_id][index]\n```\n\n\n#### Hashmap + Deepcopy\n\nThis code snippet still duplicates previous `snap_array`, thus create redundency in elements. for example:\n![image](https://user-images.githubusercontent.com/6414741/77181181-dbad7880-6ac2-11ea-80fa-5b1e5ba0f3a1.png)\nInstead of making a copy to all elements, we only need to make new copies of the elements that has been modified.\nFor the remaining unchanged elements, we can query them by a backward while loop, which increase the time complexity back to O(N)\n\nHowever the time complexity is GREAT\n\n`set() O(1)`\n`set() O(1)`\n`get() O(1)`\n\n```python\nfrom collections import defaultdict\nclass SnapshotArray(object):\n    def __init__(self, length):\n        self.dic = defaultdict(dict)\n        self.snap_id = 0\n        \n        \n    def set(self, index, val):\n        self.dic[self.snap_id][index] = val\n        \n\n    def snap(self):\n        self.snap_id += 1\n        self.dic[self.snap_id] = self.dic[self.snap_id - 1].copy()\n        return self.snap_id -1\n        \n\n    def get(self, index, snap_id):\n        if index in self.dic[snap_id]:\n            return self.dic[snap_id][index]\n        else:\n            return 0\n```\n\n\n#### Backward While Loop\n\nWe can make this search faster by replacing linear query with a binary search\n\n```python\nfrom collections import defaultdict\nclass SnapshotArray:\n    def __init__(self, length: int):\n        self.snap_id = 0\n        self.history = defaultdict(dict)\n    \n    def set(self, index: int, val: int) -> None:\n        self.history[self.snap_id][index] = val\n    \n    def snap(self) -> int:\n        self.snap_id += 1\n        return self.snap_id - 1\n    \n    def get(self, index: int, snap_id: int) -> int:\n        copy_id = snap_id\n        while copy_id > 0 and index not in self.history[copy_id]:\n            copy_id -= 1\n        if index in self.history[copy_id]:\n            return self.history[copy_id][index]\n        return 0\n```\n\n\n#### Backward Binary Search\n\nCode Snippet from @lee215\n\n```python\n    def __init__(self, n):\n        self.A = [[[-1, 0]] for _ in xrange(n)]\n        self.snap_id = 0\n\n    def set(self, index, val):\n        self.A[index].append([self.snap_id, val])\n\n    def snap(self):\n        self.snap_id += 1\n        return self.snap_id - 1\n\n    def get(self, index, snap_id):\n        i = bisect.bisect(self.A[index], [snap_id + 1]) - 1\n        return self.A[index][i][1]\n```
[]