C++ | Most Detailed Explanation | codestorywithMIK
YouTube Link - Snapshot Array\nMy Github Treasure - Snapshot Array\n\n\n//Approach-1 : Brute Force - Store all states of array for all snap ids\n//You can write
YouTube Link - [Snapshot Array](https://www.youtube.com/watch?v=yEYoNCom72Q)\nMy Github Treasure - [Snapshot Array](https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Design/Snapshot%20Array.cpp)\n\n```\n//Approach-1 : Brute Force - Store all states of array for all snap ids\n//You can write it on your own. A very simple one.\n```\n\n```\n//Approach-2 : Use Own Binary Search - O(nlogn)\nclass SnapshotArray {\npublic:\n    \n    int snap_id;\n    \n    vector<vector<pair<int, int>>> vec;\n    \n    SnapshotArray(int length) {\n        snap_id = 0;\n        \n        vec.resize(length);\n        \n        for(int i = 0; i < length; i++) {\n            \n            vec[i].push_back(make_pair(0, 0));\n            \n        }\n    }\n    \n    void set(int index, int val) {\n        \n        vec[index].push_back(make_pair(snap_id, val));\n        \n    }\n    \n    int snap() {\n        return snap_id++;\n    }\n    \n    int get(int index, int snap_id) {\n        \n        int l = 0, r = vec[index].size()-1;\n        \n        int result = 0;\n        while(l <= r) {\n            \n            int mid = l + (r-l)/2;\n            \n            if(vec[index][mid].first <= snap_id) {\n                result = vec[index][mid].second;\n                l = mid+1;\n            } else {\n                r = mid-1;\n            }\n            \n        }\n        \n        return result;\n        \n    }\n};\n```\n\n\n```\n//Approach-3 : Use upper_bound - O(nlogn)\nclass SnapshotArray {\npublic:\n    \n    int snap_id;\n    \n    vector<vector<pair<int, int>>> vec;\n    \n    SnapshotArray(int length) {\n        snap_id = 0;\n        \n        vec.resize(length);\n        \n        for(int i = 0; i < length; i++) {\n            \n            vec[i].push_back(make_pair(0, 0));\n            \n        }\n    }\n    \n    void set(int index, int val) {\n        \n        vec[index].push_back(make_pair(snap_id, val));\n        \n    }\n    \n    int snap() {\n        return snap_id++;\n    }\n    \n    int get(int index, int snap_id) {\n        \n        auto it = upper_bound(begin(vec[index]), end(vec[index]), make_pair(snap_id, INT_MAX));\n        //pair(snap_id, val)\n        \n        return prev(it)->second;\n        \n    }\n};\n```
[]