[JS] Initial and Optimised solution
Solution 1:\n\nModified Solution 2 to use Hashmap instead of an array for each element. This will reduce the space complexity, as only one value will be stored 
**Solution 1:**\n\nModified Solution 2 to use **Hashmap** instead of an array for each element. This will reduce the space complexity, as only one value will be stored for each `snap_id`.\n\n```\n// TC = O(s * n); SC = O(n + s * n)\nclass SnapshotArray {\n    constructor(length) {\n        this.elements = Array(length).fill(0);    // TC: O(n); SC = O(n)\n        this.snapshots = new Map();    // SC: O(s * n)\n        this.snapId = -1;\n    }\n    set(index, val) {   // TC: O(1)\n        this.elements[index] = val;\n    }\n    snap() {    // TC: O(n)\n        ++this.snapId;\n        this.snapshots.set(this.snapId, [...this.elements]);    // TC: O(n) [create deep copy of the array each time snapshot is called]\n        return this.snapId;\n    }\n    get(index, snap_id) {   // TC: O(1)\n        const snapshot = this.snapshots.has(snap_id) ? this.snapshots.get(snap_id) : [];\n        return index < snapshot.length ? snapshot[index] : -1;\n    }\n}\n```\nTime Complexity:\n`constructor - O(n)`\n`set - O(1)`\n`snap - O(n)`\n`get - O(1)`\n\nSpace Complexity: O(n + s * n) ~ `O(s * n)`\n[n - number of elements; s - number of snapshots taken]\n\n----\n\n**Solution 2:**\n\n```\nclass SnapshotArray {\n    constructor(length) {\n        // each element will be an array of [val, snapId] values\n        this.elements = Array(length).fill(null).map(el => []);    // O(n)\n        this.snapId = 0;\n    }\n    set(index, val) {   // O(1)\n        this.elements[index].push([val, this.snapId]);\n    }\n    snap() {    // O(1)\n        ++this.snapId;\n        return this.snapId - 1;\n    }\n\t// find the value for snapId <= snap_id. in case no value is found, return 0\n    get(index, snap_id) {   // O(log(s))\n        const element = this.elements[index];\n        let left = 0,\n            right = element.length - 1,\n            mid, id = -1;\n        \n        while(left <= right) {\n            mid = left + Math.floor((right - left) / 2);\n            if(element[mid][1] <= snap_id) {\n                id = mid;\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n        return id === -1 ? 0 : element[id][0];\n    }\n}\n```\nTime Complexity:\n`constructor - O(n)`\n`set - O(1)`\n`snap - O(1)`\n`get - O(log(s))`\n\nSpace Complexity: `O(n)`\n[n - number of elements; s - number of snapshots taken]\n\n----\n\n**Solution 3:**\n\n```\nclass SnapshotArray {\n    constructor(length) {\n        // each element will be an array of Map\n        this.elements = Array(length).fill(null).map(el => new Map());   // max O(n + s)\n        this.snapId = 0;\n    }\n    set(index, val) {   // O(1)\n        this.elements[index].set(this.snapId, val);\n    }\n    snap() {    // O(1)\n        ++this.snapId;\n        return this.snapId - 1;\n    }\n    get(index, snap_id) {   // O(log(s) + s)\n        const element = Array.from(this.elements[index].keys());    // O(s)\n        let left = 0,\n            right = element.length - 1,\n            mid, id = -1;\n        \n        while(left <= right) {\n            mid = left + Math.floor((right - left) / 2);\n            if(element[mid] <= snap_id) {\n                id = element[mid];\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n        return id === -1 ? 0 : this.elements[index].get(id);\n    }\n}\n```\nTime Complexity:\n`constructor - O(n)`\n`set - O(1)`\n`snap - O(1)`\n`get - O(log(s) + s) ~ O(s)`\n\nSpace Complexity: `O(n)`\n[n - number of elements; s - number of snapshots taken]
['Array', 'Binary Tree', 'JavaScript']