Very Easy | 2D vector | C++ | Intuition and Approach Explained
Intuition\n\nThe problem requires implementing a data structure that supports setting values at specific indices, taking snapshots of the array, and retrieving 
# Intuition\n\nThe problem requires implementing a data structure that supports setting values at specific indices, taking snapshots of the array, and retrieving values at specific indices for a given snapshot. To efficiently handle snapshots, we can use a vector of vectors to store the values along with their respective snapshot IDs.\n\n\n\n# Approach\n1. Initialize a vector of vectors, \'v\', of size \'length\', where each element is initialized with a pair {0, 0}, representing the snapshot ID and value respectively. Initialize \'snapId\' to 0.\n2. In the set() function, check if the last snapshot ID for the given index is equal to \'snapId\'. If so, update the value at that snapshot. Otherwise, push a new pair {snapId, val} into the vector for that index.\n3. In the snap() function, return \'snapId\' and increment it by 1.\n4. In the get() function, iterate through the vector for the given index. If the snapshot ID is greater than the given \'snap_id\', break the loop. Otherwise, update the answer with the current value. Return the final answer.\n\n# Complexity\n- Time complexity:\n The set() function takes O(1) time as it directly updates the vector.\n The snap() function takes O(1) time as it increments \'snapId\'.\n The get() function takes O(N) time on average, where N is the number of snapshots, as it performs a search on the vector of snapshots.\n\n- Space complexity:\n The space complexity is O(N * M), where N is the length of the array and M is the number of snapshots. Each element in the vector has a pair of snapshot ID and value.\n\nImplementation of the SnapshotArray class with the provided solution\n\n# Code\n```\nclass SnapshotArray {\n    vector<vector<pair<int,int>>> v;\n    int snapId;\npublic:\n    SnapshotArray(int length) {\n        v.resize(length,vector<pair<int,int>>(1,{0,0}));\n        snapId=0;\n    }\n    \n    void set(int index, int val) {\n\n        if(v[index].back().first == snapId){\n            v[index].back().second = val;\n        }\n        else{\n            v[index].push_back({snapId,val});\n        }\n    }\n    \n    int snap() {\n        return snapId++;\n\n    }\n    \n    int get(int index, int snap_id) {\n        int ans=0;\n        for(auto a:v[index]){\n            if(a.first>snap_id){\n                break;\n            }\n            ans=a.second;\n        }\n        return ans;\n    }\n};\n\n/**\n * Your SnapshotArray object will be instantiated and called as such:\n * SnapshotArray* obj = new SnapshotArray(length);\n * obj->set(index,val);\n * int param_2 = obj->snap();\n * int param_3 = obj->get(index,snap_id);\n */\n```
['C++']