Java HashMap solution (optimal) - Concept Explained and Commented
There\'s different method\'s we can go about this problem. The first, most intuitive way would be to create an array and keep updating that array, then store a 
There\'s different method\'s we can go about this problem. The first, most intuitive way would be to create an array and keep updating that array, then store a copy of that array in a hashmap for each snapshot. But, we would be storing a lot of unnecessary information, wasting memory. If we never update index 0, do we really need to store the information about index 0? \n\nWe really just need to keep track of any changes that are made to the array in each snapshot. Let\'s call this a deltaUpdate. We also need a history of updates made to each index everytime it was saved. Let\'s keep track of the value of each index at each snapshot. How do we do that? Lets keep a HashMap, mapping each snap_id to the value AT EACH index. But lets only update that history when there is an update between two snapshots (using our deltaUpdate which keeps track of changes made between snapshots). Otherwise, we know that its value should\'ve been stored at its most recent snapshot before the current snapshot, if it was ever updated. \n\n```\nclass SnapshotArray {\n    //map <Snap_id , Value> for each index (array of maps)\n    HashMap<Integer,Integer> [] snapShotHistory;\n    \n    //totalSnaps taken\n    int totalSnaps;\n\n    //map of delta updates made <index, value>\n    HashMap<Integer,Integer> deltaUpdate;\n    \n    public SnapshotArray(int length) {\n        //keep track of the delta updates made in each iteration\n        deltaUpdate=new HashMap<>();\n        \n        //initialize a snapshot history\n        snapShotHistory=new HashMap[length];\n        for(int i=0; i<length; i++){\n            snapShotHistory[i]=new HashMap<>();\n        }\n    }\n    \n    public void set(int index, int val) {\n        //add a delta update for this index, value pair\n        deltaUpdate.put(index,val);\n    }\n    \n    public int snap() {\n        //add the current mapping at each index, value pair\n        for (int key: deltaUpdate.keySet()){\n            HashMap<Integer, Integer> snapHistoryAtIndex = snapShotHistory[key];\n            //add a snapshot of the <snapId, value> to the index updated\n            snapHistoryAtIndex.put(totalSnaps, deltaUpdate.get(key));\n        }\n        \n        //reset out delta update map\n        deltaUpdate=new HashMap<>();\n        \n        //incremement our total snaps and return the snap id\n        totalSnaps++;\n        return totalSnaps-1;\n    }\n    \n    public int get(int index, int snap_id) {\n        //find the most recent update to that index from the snapId specified and before\n        while(snap_id>=0){\n            if(snapShotHistory[index].containsKey(snap_id))\n                 return snapShotHistory[index].get(snap_id);\n            snap_id--;\n        }\n        \n        //if there was never an update to that index, it will just be equal to 0\n        return 0;\n    }\n}\n```
['Java']