✅Simple Java✔ || C++✔ ||Python✔ ||  Easy To Understand
Please Vote up :))\nFor this problem we need to optimize on space so we can\'t tradeoff memory for time. If you save the whole array for every snapshot there wi
# Please Vote up :))\n**For this problem we need to optimize on space so we can\'t tradeoff memory for time. If you save the whole array for every snapshot there will be "Memory limit exceeded" error.\n\nEssentially we are interested only in history of changes for the index, and it could be only few changes of one index. This means we need to lookup effectively value by index and save only those that changed. We can use Map for this, use index as key, value as a value.\n\nWe keep such map for every snapshot, each consequence change will override previous value but this is perfectly fine - we care only about last value. We keep maps in a list, index of the element is a snapshot index.\n\nOn value lookup we start scanning list elements starting from the passed snapshot_id back to 0. Return first value for the index that we found - this means the most recent change up to this snapshot_id. If we haven\'t found anything it means there were no changes and we can return initial value which is 0 for all elements.\n\nO(1) for set - lookup for the map is O(1), put to the map is O(1) (average).\nO(snap_id) for get() - we can potentially search up to snap_id snapshots (maps in our list), then O(1) for the lookup by index.\nO(length^2) for space - we can save every element in map, then change every element for every snapshot**\n\n# Approach\nHere\'s a brief explanation of the approach:\n\n    The array variable is initialized as a list of lists, where each element represents the history of a specific index. Each history entry is a tuple (snap_id, value) that records the value at that index and the snapshot ID when it was set.\n\n    The set method appends a new history entry to the corresponding index in the array, using the current snap_id and the provided value.\n\n    The snap method increments the snap_id and returns the previous snap_id, which represents the total number of snapshots taken minus 1.\n\n    The get method searches for the closest snapshot index in the history of the specified index using binary search. It then returns the value recorded at that snapshot index.\n\nThis implementation provides efficient snapshots by only storing the changed values at each index and using binary search for retrieval, resulting in O(log N) time complexity for the get method, where N is the number of snapshots taken.\n\n\n\n#  JAVA Code\n```\nclass SnapshotArray {\n    TreeMap<Integer, Integer>[] Tm;\n    int snap_id = 0;\n    public SnapshotArray(int length) {\n        Tm = new TreeMap[length];\n        for (int i = 0; i < length; i++) {\n            Tm[i] = new TreeMap<Integer, Integer>();\n            Tm[i].put(0, 0);\n        }\n    }\n\n    public void set(int index, int val) {\n        Tm[index].put(snap_id, val);\n    }\n\n    public int snap() {\n        return snap_id++;\n    }\n\n    public int get(int index, int snap_id) {\n        return Tm[index].floorEntry(snap_id).getValue();\n    }\n}\n\n\n```\n\n\n\n\n# C++ Code\n\n\n```\nclass SnapshotArray {\n    vector<vector<pair<int, int>>>updates;\n    int curSnap;\n\npublic:\n    SnapshotArray(int length) {\n        updates.resize(length);\n        curSnap = 0;\n    }\n\n    void set(int index, int val) {\n        if (!updates[index].empty() && updates[index].back().first == curSnap)\n            updates[index].back().second = val;\n        else\n            updates[index].push_back({curSnap, val});\n    }\n\n    int snap() {\n        curSnap++;\n        return curSnap - 1;\n    }\n\n    int get(int index, int snap_id) {\n        int idx = upper_bound(updates[index].begin(), updates[index].end(), make_pair(snap_id,INT_MAX)) - updates[index].begin();\n        if (idx == 0) return 0;\n        return updates[index][idx - 1].second;\n    }\n};\n\n```\n\n\n# Python Code\n\n\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.cur_id = 0\n        self.curVals = [0] * length\n        self.snapIdArr = [[-1] for _ in range(length)]\n        self.arrVal = [[0] for _ in range(length)]\n        self.modified = set()\n\n    def set(self, index: int, val: int) -> None:\n        if val == self.arrVal[index][-1]:\n            if index in self.modified: self.modified.remove(index)\n            return\n        self.curVals[index] = val\n        if index not in self.modified: self.modified.add(index)\n\n    def snap(self) -> int:\n        for idx in self.modified:\n            self.snapIdArr[idx].append(self.cur_id)\n            self.arrVal[idx].append(self.curVals[idx])\n        self.modified.clear()\n        self.cur_id += 1\n        return self.cur_id - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n        arr = self.snapIdArr[index]\n        l, r = 0, len(arr)\n        while l < r:\n            m = (l + r) // 2\n            if arr[m] <= snap_id:\n                l = m + 1\n            else: r = m\n        return self.arrVal[index][l-1]\n\n\n\n```
['Binary Search', 'Python', 'C++', 'Java', 'Python3']