Rust. Time complexity: O(log S), space complexity O(N)
Intuition\n\nAt a first glance the problem can be solved by duplicating the array every time you get a snap, and then looking for a value in the corresponding s
# Intuition\n\nAt a first glance the problem can be solved by duplicating the array every time you get a snap, and then looking for a value in the corresponding snap.\n\nIn this case every operation (both reads and writes) would have a constant time complexity `O(1)`.\n\nThe problem with this naive approach is it consumes a lot of memory, becasue even though nothing can be changed between snaps you\'d have to duplicate the array.\n\nThe memory complexity would be `O(N * S)` where the `N` is the size of the array, and the `S` is the number of snaps been taken.\n\nSo the **challenge** we face is how to store only the necessary changes, and at the same time keep the r/w operations fast enough.\n\nBecause each value changes individually, the natural approach is to store the stream of changes of **every individual item** as an array-like structure (`Vec` in Rust, or `Array` in Ruby).\n\nThe array as a whole can be represented as `Vec<Vec<(usize, i32)>>` where `usize` keeps `snap_id`, `i32` keeps the corresponding value.\n\n# Approach\n\nTo keep the corresponding `snap_id` for every snapshot value, you can either use the same structure (`Vec<(usize, i32)>`), or 2 parallel structures for `values` and `snap_ids`, having the same length.\n\nThat said, in our structure we have to keep:\n- the snapshot values as `Vec<Vec<i32>>`\n- the corresponding snapshot ids `Vec<Vec<usize>>`\n- the current `snap_id: usize`\n\nExample:\n\n```rust\n#[derive(Debug)]\nstruct SnapshotArray {\n    // the list of snapshot values for every array element\n    // a new value is either overwrite the last snapshot\n    // if the snap hasn\'t changed, or add the new one\n    values:   Vec<Vec<i32>>,\n    // the list of snapshot ids for every individual value\n    snap_ids: Vec<Vec<usize>>,\n    // the list of \n    snap_id:  usize,\n}\n```\n\nThe algorithms are simple\n\n- **Initialize** the structure with \n    - `vec![vec![0i32]; lenght]`, keeping the first `0i32` for every element\n    - `vec![vec![0usize; length]]` keeping the `0usize` snap_id for every snapshot value\n    - `0usize` as the current `snap_id`\n\n- **Take the snap** by increasing `snap_id`\n\n- **Insert the value** by checking if the last snapshot in the `snap_ids[index]` equals the current `snap_id`. If yes, we overwrite the last value in `values[index]`, otherwise add new snapshot to the `values[index]` and new snap_id to the `snap_ids[index]`.\n\n- **Look for the value** requires to find the `snap`, not greater, than an interesting version, in the `snap_ids[index]`. Then take the value from `values[index][snap]`.\n\n# Complexity\n- Time complexity:\n\n    - initialize `O(1)`\n    - take a snap `O(1)`\n    - insert value `O(1)` (either update or insert a value to the tail of the list / `Vec`)\n    - find value `O(log S)` (binary search of the `snap_id` in the corresponding `snap_ids[index]`)\n\n- Space complexity:\n\n    `O(M)` where `M` is the total number of changes of elements between snaps.\n\n# Code\n\n```rust\n#[derive(Debug)]\nstruct SnapshotArray {\n    values:   Vec<Vec<i32>>,\n    snap_ids: Vec<Vec<usize>>,\n    snap_id:  usize,\n}\n\nimpl SnapshotArray {\n    fn new(length: i32) -> Self {\n        let length = length as usize;\n        Self {\n            values:   vec![vec![0]; length],\n            snap_ids: vec![vec![0]; length],\n            snap_id:  0,\n        }        \n    }\n    \n    fn set(&mut self, index: i32, val: i32) {\n        let index = index as usize;\n        let last_snap = self.snap_ids[index].len() - 1;\n\n        if self.snap_ids[index][last_snap] == self.snap_id {\n            self.values[index][last_snap] = val;\n        } else {\n            self.snap_ids[index].push(self.snap_id);\n            self.values[index].push(val);\n        }\n    }\n    \n    fn snap(&mut self) -> i32 {\n        self.snap_id += 1;\n        self.snap_id as i32 - 1\n    }\n    \n    fn get(&self, index: i32, snap_id: i32) -> i32 {\n        let (index, snap_id) = (index as usize, snap_id as usize);\n\n        match self.snap_ids[index].binary_search(&snap_id) {\n            Err(snap) => self.values[index][snap-1],\n            Ok(snap)  => self.values[index][snap],\n        }\n    }\n}\n```
['Rust']