[Java] 3 Solutions, Binary search, TreeMap, ArrayCopy
List + Binary Search Solution\n\n// List + Binary Search Solution\n// Space complexity: O(C), where C is the number of changes\nclass SnapshotArray {\n    priva
List + Binary Search Solution\n```\n// List + Binary Search Solution\n// Space complexity: O(C), where C is the number of changes\nclass SnapshotArray {\n    private List<int[]>[] records;  // list of record, record the (snap_id, value) tuple. snap_id increased.\n    private int snapIdx;\n    \n    public SnapshotArray(int length) {\n        records = new ArrayList[length];\n        for (int i = 0; i < length; i++) {\n            records[i] = new ArrayList<>();\n            records[i].add(new int[]{0, 0});\n        }\n    }\n    \n    // Time complexity: O(1)\n    public void set(int index, int val) {\n        List<int[]> record = records[index];\n        int[] last = record.get(record.size() - 1);\n        if (last[0] == snapIdx) {\n            last[1] = val;\n        } else {\n            record.add(new int[]{snapIdx, val});\n        }\n    }\n    \n    // Time complexity: O(1)\n    public int snap() {\n        return snapIdx++;\n    }\n    \n    // Time complexity: O(logN)\n    public int get(int index, int snap_id) {\n        List<int[]> record = records[index];\n        int idx = Collections.binarySearch(record, \n                                           new int[]{snap_id, 0},\n                                           (r1, r2) -> Integer.compare(r1[0], r2[0]));\n        if (idx < 0) idx = -idx - 2;\n        return record.get(idx)[1];\n    }\n}\n```\n\nTreeMap Solution\n```\n// TreeMap Solution\n// Space complexity: O(C), where C is the number of changes\nclass SnapshotArray {\n    private TreeMap<Integer, Integer>[] maps;  // index: <snap_id, val>\n    private int snapIdx;\n\n    // Time complexity: O(N)\n    public SnapshotArray(int length) {\n        maps = new TreeMap[length];\n        for (int i = 0; i < length; i++) {\n            maps[i] = new TreeMap<>();\n            maps[i].put(0, 0);\n        }\n    }\n    \n    // Time complexity: O(logN)\n    public void set(int index, int val) {\n        TreeMap<Integer, Integer> map = maps[index];\n        map.put(snapIdx, val);\n    }\n    \n    // Time complexity: O(1)\n    public int snap() {\n        return snapIdx++;\n    }\n    \n    // Time complexity: O(logN)\n    public int get(int index, int snap_id) {\n        TreeMap<Integer, Integer> map = maps[index];\n        return map.floorEntry(snap_id).getValue();\n    }\n}\n```\n\nArrayCopy Solution\n```\n// ArrayCopy Solution: no enough memory\n// Space complexity: O(N * S), where S is the number of snaps\nclass SnapshotArray {\n    private int snapId;\n    private int[] arr;\n    private Map<Integer, int[]> map;\n\n    // Time complexity: O(N)\n    public SnapshotArray(int length) {\n        arr = new int[length];\n        map = new HashMap<>();\n    }\n    \n    // Time complexity: O(1)\n    public void set(int index, int val) {\n        // ask what if index is out of bound.\n        arr[index] = val;\n    }\n    \n    // Time complexity: O(N)\n    public int snap() {\n        int id = snapId;\n        snapId++;\n        int[] snapArr = new int[arr.length];\n        System.arraycopy(arr, 0, snapArr, 0, arr.length);\n        map.put(id, snapArr);\n        return id;\n    }\n    \n    // Time complexity: O(1)\n    public int get(int index, int snap_id) {\n        // ask what if snap_id is not exist.\n        // ask what if index is out of bound.\n        int[] snapArr = map.get(snap_id);\n        return snapArr[index];\n    }\n}\n```
['Java']