# Snapshot Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/snapshot-array)
Canonical: https://scaleengineer.com/dsa/problems/snapshot-array
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Snowflake](https://scaleengineer.com/companies/snowflake), [Coupang](https://scaleengineer.com/companies/coupang), [Databricks](https://scaleengineer.com/companies/databricks), [Rubrik](https://scaleengineer.com/companies/rubrik), [Verkada](https://scaleengineer.com/companies/verkada), [StackAdapt](https://scaleengineer.com/companies/stackadapt)
---
## Problem
Implement a SnapshotArray that supports the following interface:

* `SnapshotArray(int length)` initializes an array-like data structure with the given length. **Initially, each element equals 0**.
* `void set(index, val)` sets the element at the given `index` to be equal to `val`.
* `int snap()` takes a snapshot of the array and returns the `snap_id`: the total number of times we called `snap()` minus `1`.
* `int get(index, snap_id)` returns the value at the given `index`, at the time we took the snapshot with the given `snap_id`

**Example 1:**

**Input:** ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
**Output:** [null,null,0,null,5]
**Explanation:** 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

**Constraints:**

* `1 <= length <= 5 * 104`
* `0 <= index < length`
* `0 <= val <= 109`
* `0 <= snap_id < `(the total number of times we call `snap()`)
* At most `5 * 104` calls will be made to `set`, `snap`, and `get`.

# Approaches
## Brute Force: Full Array Copy on Snap
This approach is the most straightforward and intuitive. We maintain a current version of the array. Every time `snap()` is called, we create a complete, deep copy of the current array and store it in a map, using the `snap_id` as the key. This ensures that we have a perfect record of the array's state for each snapshot.
**Time:** - **Constructor**: O(L) to initialize the array.
- **`set`**: O(1).
- **`snap`**: O(L) due to the array copying.
- **`get`**: O(1) for HashMap lookup. · **Space:** O(S * L), where S is the number of snapshots and L is the array length. This is because for each of S snapshots, we store a full copy of the array of length L.
**Pros:** Simple to understand and implement.; `set` and `get` operations are very fast (O(1)).
**Cons:** `snap()` operation is slow, with a time complexity of O(L), where L is the length of the array.; Extremely high space complexity (O(S * L), where S is the number of snapshots), making it infeasible for large inputs.
### Explanation
In this method, we use a simple integer array, let's call it `current_array`, to store the most recent state of the data. A `HashMap<Integer, int[]>` named `snapshots` is used to store the historical versions of the array, where the key is the `snap_id` and the value is the array state at that snapshot. A counter `snap_id` tracks the number of snapshots taken.

- **`SnapshotArray(length)`**: Initializes `current_array` of the given length with zeros, initializes the `snapshots` map, and sets `snap_id` to 0.
- **`set(index, val)`**: Updates the value in `current_array` at the given index. This is a constant time operation.
- **`snap()`**: This is the core of this approach. It creates a deep copy of `current_array` and stores it in the `snapshots` map with the current `snap_id`. It then increments `snap_id` and returns the ID of the snapshot just created. The copy operation takes time proportional to the length of the array.
- **`get(index, snap_id)`**: Retrieves the array corresponding to the given `snap_id` from the `snapshots` map and then returns the element at the specified `index`.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class SnapshotArray {
    private int[] current_array;
    private Map<Integer, int[]> snapshots;
    private int snap_id;

    public SnapshotArray(int length) {
        current_array = new int[length];
        snapshots = new HashMap<>();
        snap_id = 0;
    }

    public void set(int index, int val) {
        current_array[index] = val;
    }

    public int snap() {
        int[] copy = Arrays.copyOf(current_array, current_array.length);
        snapshots.put(snap_id, copy);
        return snap_id++;
    }

    public int get(int index, int snap_id) {
        int[] snapshot_array = snapshots.get(snap_id);
        return snapshot_array[index];
    }
}
```
### Algorithm
- Initialize `current_array` of size `length`, a `HashMap<Integer, int[]> snapshots`, and `snap_id = 0`.
- **`set(index, val)`**: Update `current_array[index] = val`.
- **`snap()`**:
  1. Create a copy: `int[] copy = Arrays.copyOf(current_array, length)`.
  2. Store the copy: `snapshots.put(snap_id, copy)`.
  3. Return `snap_id++`.
- **`get(index, snap_id)`**:
  1. Retrieve the snapshot: `int[] snapshot_array = snapshots.get(snap_id)`.
  2. Return `snapshot_array[index]`.

## Optimized: History Tracking with Binary Search
This approach optimizes space and time by avoiding full array copies. Instead of storing the entire array for each snapshot, we only record the changes made to each element. For each index in the array, we maintain a history of its values, mapping the `snap_id` at which a value was set to the value itself. This is a 'copy-on-write' strategy applied at the element level rather than the array level.
**Time:** - **Constructor**: O(L) to initialize the array of TreeMaps.
- **`set`**: O(log K), where K is the number of times `set` has been called for that specific index.
- **`snap`**: O(1).
- **`get`**: O(log K), where K is the number of historical entries for that index, due to the binary search nature of `TreeMap.floorEntry`. · **Space:** O(C_set), where `C_set` is the total number of calls to `set`. We only store the values that are explicitly set, not full arrays.
**Pros:** Highly efficient `snap()` operation (O(1)).; Massively reduced space complexity compared to the brute-force approach.; `set` and `get` are still very fast (logarithmic time).
**Cons:** Slightly more complex to implement and reason about than the brute-force approach.; `set` and `get` are not O(1), but O(log K), though this is negligible in practice.
### Explanation
The primary data structure is an array of `TreeMap`s, let's say `history = new TreeMap[length]`. Each `history[i]` will store the value history for the element at index `i`. A `TreeMap` is chosen because it keeps entries sorted by key (`snap_id`) and provides an efficient way (`floorEntry`) to find the relevant value for a given snapshot.

- **`SnapshotArray(length)`**: Initializes the `history` array. For each index `i`, a new `TreeMap` is created. To handle the initial state where all values are 0, we add an entry `(0, 0)` to each `TreeMap`. This signifies that at `snap_id` 0 (and before any `set` calls), the value is 0.
- **`set(index, val)`**: When a value is set at a particular index, we record this change in the corresponding `TreeMap`. We add or update the entry for the *current* `snap_id`: `history[index].put(snap_id, val)`. This operation takes logarithmic time relative to the number of changes for that index.
- **`snap()`**: This operation becomes extremely efficient. We simply increment the `snap_id` counter and return its previous value. No data copying is needed. This is a constant time operation.
- **`get(index, snap_id)`**: To get the value of an element at a specific snapshot, we look into its history `TreeMap`, `history[index]`. We need to find the value that was set at or before the requested `snap_id`. The `TreeMap.floorEntry(snap_id)` method is perfect for this; it finds the entry with the greatest key (snap_id) that is less than or equal to the given `snap_id`. We then return the value from this entry. Because we pre-populated the `TreeMap` with `(0, 0)`, `floorEntry` will always find a valid entry for any non-negative `snap_id`.

An alternative to `TreeMap` is using a `List` of pairs `(snap_id, value)` for each index. Since `set` calls for an index will have increasing `snap_id`s, the list will be sorted. `get` can then use binary search on this list. The performance characteristics are nearly identical.

```java
import java.util.TreeMap;

class SnapshotArray {
    private TreeMap<Integer, Integer>[] history;
    private int snap_id;

    public SnapshotArray(int length) {
        history = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            history[i] = new TreeMap<>();
            history[i].put(0, 0); // Initial value at snap_id 0 is 0
        }
        snap_id = 0;
    }

    public void set(int index, int val) {
        history[index].put(snap_id, val);
    }

    public int snap() {
        return snap_id++;
    }

    public int get(int index, int snap_id) {
        // Find the value at the greatest snap_id <= the given snap_id
        return history[index].floorEntry(snap_id).getValue();
    }
}
```
### Algorithm
- Initialize `history`, an array of `TreeMap<Integer, Integer>` of size `length`.
- For each index `i`, initialize `history[i]` and add an initial entry: `history[i].put(0, 0)`.
- Initialize `snap_id = 0`.
- **`set(index, val)`**: Record the change: `history[index].put(snap_id, val)`.
- **`snap()`**: Increment and return the snap ID: `return snap_id++`.
- **`get(index, snap_id)`**:
  1. Find the relevant history entry using binary search: `Map.Entry<Integer, Integer> entry = history[index].floorEntry(snap_id)`.
  2. Return the value from the entry: `return entry.getValue()`.

# Solutions
### Java

```java
class SnapshotArray { private List < int []>[] arr ; private int idx ; public SnapshotArray ( int length ) { arr = new List [ length ]; Arrays . setAll ( arr , k -> new ArrayList <>()); } public void set ( int index , int val ) { arr [ index ]. add ( new int [] { idx , val }); } public int snap () { return idx ++; } public int get ( int index , int snap_id ) { var vals = arr [ index ]; int left = 0 , right = vals . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( vals . get ( mid )[ 0 ] > snap_id ) { right = mid ; } else { left = mid + 1 ; } } return left == 0 ? 0 : vals . get ( left - 1 )[ 1 ]; } } /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray obj = new SnapshotArray(length); * obj.set(index,val); * int param_2 = obj.snap(); * int param_3 = obj.get(index,snap_id); */
```

### CPP

```cpp
class SnapshotArray { public: SnapshotArray ( int length ) { idx = 0 ; arr = vector < vector < pair < int , int >>> ( length ); } void set ( int index , int val ) { arr [ index ]. push_back ({ idx , val }); } int snap () { return idx ++ ; } int get ( int index , int snap_id ) { auto & vals = arr [ index ]; int left = 0 , right = vals . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( vals [ mid ]. first > snap_id ) { right = mid ; } else { left = mid + 1 ; } } return left == 0 ? 0 : vals [ left - 1 ]. second ; } private: vector < vector < pair < int , int >>> arr ; int idx ; }; /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */
```

### Python

```python
class SnapshotArray : def __init__ ( self , length : int ): self . idx = 0 self . arr = defaultdict ( list ) def set ( self , index : int , val : int ) -> None : self . arr [ index ]. append (( self . idx , val )) def snap ( self ) -> int : self . idx += 1 return self . idx - 1 def get ( self , index : int , snap_id : int ) -> int : vals = self . arr [ index ] i = bisect_right ( vals , ( snap_id , inf )) - 1 return 0 if i < 0 else vals [ i ][ 1 ] # Your SnapshotArray object will be instantiated and called as such: # obj = SnapshotArray(length) # obj.set(index,val) # param_2 = obj.snap() # param_3 = obj.get(index,snap_id)
```