Code Implementation

class SnapshotArray:
    def __init__(self, length: int):
        self.snaps = 0
        self.data = [{} for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.data[index][self.snaps] = val

    def snap(self) -> int:
        self.snaps += 1
        return self.snaps - 1

    def get(self, index: int, snap_id: int) -> int:
        d = self.data[index]
        # Find the latest snap_id <= requested snap_id
        while snap_id not in d and snap_id >= 0:
            snap_id -= 1
        return d.get(snap_id, 0)
      

class SnapshotArray {
public:
    vector<vector<pair<int, int>>> arr;
    int snap_id = 0;
    SnapshotArray(int length) {
        arr.resize(length);
        for (int i = 0; i < length; ++i)
            arr[i].push_back({0, 0});
    }
    
    void set(int index, int val) {
        if (arr[index].back().first == snap_id)
            arr[index].back().second = val;
        else
            arr[index].push_back({snap_id, val});
    }
    
    int snap() {
        return snap_id++;
    }
    
    int get(int index, int snap_id) {
        auto& v = arr[index];
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int m = (l + r + 1) / 2;
            if (v[m].first <= snap_id) l = m;
            else r = m - 1;
        }
        return v[l].second;
    }
};
      

class SnapshotArray {
    private List<TreeMap<Integer, Integer>> data;
    private int snapId;

    public SnapshotArray(int length) {
        data = new ArrayList<>();
        for (int i = 0; i < length; ++i) {
            TreeMap<Integer, Integer> map = new TreeMap<>();
            map.put(0, 0);
            data.add(map);
        }
        snapId = 0;
    }

    public void set(int index, int val) {
        data.get(index).put(snapId, val);
    }

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

    public int get(int index, int snap_id) {
        Map.Entry<Integer, Integer> entry = data.get(index).floorEntry(snap_id);
        return entry == null ? 0 : entry.getValue();
    }
}
      

var SnapshotArray = function(length) {
    this.snaps = 0;
    this.data = Array.from({length}, () => new Map([[0, 0]]));
};

SnapshotArray.prototype.set = function(index, val) {
    this.data[index].set(this.snaps, val);
};

SnapshotArray.prototype.snap = function() {
    return this.snaps++;
};

SnapshotArray.prototype.get = function(index, snap_id) {
    let m = this.data[index];
    while (!m.has(snap_id) && snap_id >= 0) snap_id--;
    return m.get(snap_id) ?? 0;
};
      

Problem Description

The Snapshot Array problem asks you to design a data structure that works like an array but supports versioning. Specifically, you need to:

• Initialize an array of length length with all values set to 0.
• Implement a set(index, val) method to set the value at index to val.
• Implement a snap() method that takes a snapshot of the array, returning the snap_id (starting from 0 and increasing by 1 each time).
• Implement a get(index, snap_id) method to get the value at index at the time when snap_id was taken.

Key constraints:

• You may have up to 50,000 calls to set, snap, and get each.
• Array length can be up to 50,000.
• Each snap_id is unique and refers to a single snapshot.
• All get queries refer to a valid snap_id previously returned by snap().

Thought Process

At first glance, you might think to store a copy of the entire array every time snap() is called, and then retrieve the value for get() from the corresponding snapshot. However, this brute-force approach would use too much memory, especially if only a few values change between snapshots.

To optimize, we should notice that most of the array stays the same between snapshots. So, instead of copying the whole array, we can store only the changes (also called "deltas") for each index, tracking when each value was changed.

This leads to the idea of, for each array index, keeping a history of its value changes along with the snap_id when each change occurred. When we need to get() a value for a particular snap_id, we can look up the most recent value at or before that snap_id.

Solution Approach

We solve the problem by using a data structure that, for each array index, keeps track of the values set along with the corresponding snap_id when the value was set. Here is how we design the solution:

1. Initialization:
   • For each index, we store a mapping (or list) from snap_id to value.
   • Initially, for all indices, the value at snap_id = 0 is 0.
2. Set Operation:
   • When set(index, val) is called, we record the value val at the current snap_id for that index.
   • If multiple set calls are made before a snap(), we only need to keep the latest value for the current snap_id.
3. Snap Operation:
   • When snap() is called, increment the global snap_id and return the previous value as the snapshot identifier.
4. Get Operation:
   • When get(index, snap_id) is called, we look up the value at the largest snap_id less than or equal to the requested snap_id for that index.
   • This can be efficiently done using binary search or a TreeMap (depending on the language and implementation).
   • If no value was set at or before that snap_id, return 0 (the default).

This structure ensures that we only store the changes, making both time and space usage efficient. For fast retrieval, we use binary search or data structures like TreeMap or Map, which can efficiently find the value for a given snap_id.

Example Walkthrough

Let's walk through an example:

• Initialize: SnapshotArray(3) → array is [0, 0, 0]
• set(0, 5) → array becomes [5, 0, 0] (at snap_id 0, index 0 is 5)
• snap() → returns 0
• set(0, 6) → array becomes [6, 0, 0] (at snap_id 1, index 0 is 6)
• get(0, 0) → returns 5 (for snap_id 0, index 0 was set to 5)

Here's how the internal structure evolves:

• After set(0, 5): index 0 history = {0: 5}
• After snap(): snap_id becomes 1
• After set(0, 6): index 0 history = {0: 5, 1: 6}
• On get(0, 0): find the value at snap_id 0 for index 0, which is 5

Time and Space Complexity

Brute-force approach:

• Time: O(1) for set and snap; O(1) for get if we store complete arrays per snapshot.
• Space: O(N \times S), where N is the array length and S is number of snapshots. This can be huge if both are large.

• Time:
  • set: O(1)
  • snap: O(1)
  • get: O(\log K) for binary search among K changes at an index
• Space: O(M), where M is the total number of set calls (since we only store changes, not the full array each time).

This makes the approach efficient enough for the largest constraints in the problem.

Summary

The Snapshot Array problem is solved efficiently by storing only the values that change at each index, along with the snap_id at which the change occurred. This allows us to reconstruct the state of the array at any snapshot without storing redundant data. By using maps or lists with binary search, we can quickly find the correct value for any get query. The elegance of this solution lies in leveraging the sparsity of changes and efficient data lookups, resulting in optimal time and space complexity for large-scale inputs.