Java, list and map, explained, clean, beats 95%
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 
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```\n    List<Map<Integer, Integer>> list;\n    \n    public SnapshotArray(int length) {\n        list = new ArrayList();\n        list.add(new HashMap());\n    }\n    \n    public void set(int index, int val) {\n        int snapId = list.size() - 1;\n        list.get(snapId).put(index, val);\n    }\n    \n    public int snap() {\n        list.add(new HashMap());\n        return list.size() - 2;\n    }\n    \n    public int get(int index, int snap_id) {\n        for (int snap = snap_id; snap >= 0; snap--) {\n            if (list.get(snap).containsKey(index))\n                return list.get(snap).get(index);\n        }\n        return 0;\n    }\n```
['Java']