Best Python3 Solution ≈100%Time & ≈90%Memory
Intuition\n Describe your first thoughts on how to solve this problem. \nKeep only necessary things!\n\n# Approach\n Describe your approach to solving the probl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nKeep only necessary things!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse dictionary for current values of array and use list for snapshot. Dictionary is also fine for snapshot.\n\nKey here is to save space when taking snapshot. **Use new memory for new snapshot only if it is different from old snapshot.**\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ for copying current array to snapshot\notherwise $$O(1)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(k * n)$$ where k is the number of snapshots taken and n is the number of unique indexes that have been set\n\n# Code\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.arr = dict()\n        self.snapshot = []\n        self.updated = True\n\n    def set(self, index: int, val: int) -> None:\n        self.arr[index] = val\n        self.updated = True\n\n    def snap(self) -> int:            \n        if self.updated:\n            self.snapshot.append({**self.arr})\n        else:\n            self.snapshot.append(self.snapshot[-1])\n        self.updated = False\n        return len(self.snapshot)-1\n\n    def get(self, index: int, snap_id: int) -> int:\n        return self.snapshot[snap_id].get(index, 0)\n\n\n# Your SnapshotArray object will be instantiated and called as such:\n# obj = SnapshotArray(length)\n# obj.set(index,val)\n# param_2 = obj.snap()\n# param_3 = obj.get(index,snap_id)\n```
['Array', 'Hash Table', 'Python3']