[1146. Snapshot Array](https://leetcode.com/problems/snapshot-array/)

--- tags: leetcode --- # [1146. Snapshot Array](https://leetcode.com/problems/snapshot-array/) --- # My Solution ## The Key Idea for Solving This Coding Question ## C++ Code ```cpp= struct valueData { int value; int snapId; valueData(int value, int snapId) : value(value), snapId(snapId) {} }; class SnapshotArray { public: SnapshotArray(int length) : snapId(0), length(length) {} void set(int index, int val) { auto iter = array.find(index); if (iter == array.end()) { array[index].push_back(valueData(val, snapId)); return; } vector<valueData> &valueList = iter->second; if (valueList.back().snapId == snapId) { valueList.back().value = val; return; } // valueList.back().snapId < snapId is true. valueList.push_back(valueData(val, snapId)); } int snap() { return snapId++; } int get(int index, int snap_id) { auto iter = array.find(index); if (iter == array.end()) { return 0; } vector<valueData> &valueList = iter->second; if (snap_id < valueList[0].snapId) { return 0; } //if (valueList.back().snapId <= snap_id) { // return valueList.back().value; //} // Use binary search to find a snapId that is less than // or equal to snap_id. int left = 0, right = valueList.size() - 1; while (left < right) { int middle = left + (right - left + 1) / 2; if (snap_id < valueList[middle].snapId) { right = middle - 1; } else { left = middle; } } if (snap_id < valueList[left].snapId) { --left; } return valueList[left].value; } private: int snapId; int length; unordered_map<int, vector<valueData>> array; }; /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */ ``` ## Time Complexity * `SnapshotArray` $O(1)$ * `set` $O(1)$ * `get` $O(logn)$ $n$ is the maximum number of the values. ## Space Complexity * `SnapshotArray` $O(1)$ * `set` $O(m \cdot n)$ $m$ is the value of `length`, which is the parameter of `SnapshotArray`. * `get` $O(1)$ # Miscellaneous