Problem statement

Implement an array that can take snapshots of itself and later read any element as it was in any snapshot.

Write the class SnapshotArray:

• SnapshotArray(int length) creates an array of length elements, all 0.
• void set(int index, int value) sets the element at index to value.
• int snap() takes a snapshot and returns its id: the number of times snap had been called before (so the first snapshot is 0).
• int get(int index, int snapId) returns the value the element at index had when snapshot snapId was taken.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["SnapshotArray","set","snap","set","get","get"]
[[3],[0,5],[],[0,6],[0,0],[1,0]]
Output: [null,null,0,null,5,0]
Explanation: Snapshot 0 is taken while element 0 is 5; setting it to 6 afterwards does not change snapshot 0. Element 1 was never set, so it is 0.

Example 2

Input: ["SnapshotArray","snap","set","set","snap","snap","get","get","get"]
[[2],[],[1,4],[1,7],[],[],[1,0],[1,1],[1,2]]
Output: [null,0,null,null,1,2,0,7,7]
Explanation: Snapshot 0 is taken before anything is set. Element 1 is set twice before snapshot 1, which keeps the last value, 7; snapshot 2 sees the same 7.

Constraints

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= value <= 10^9
• 0 <= snapId < the number of snap calls made so far
• At most 5 * 10^4 calls are made to set, snap and get

Hints for Snapshot Array

1. Hint 1

   Copying the whole array on every snapshot costs O(length) per snap — far too much. Most elements do not change between snapshots.

2. Hint 2

   Store, for each index, only its changes: a list of (snapshot id, value) pairs in the order they happened. Several sets before the same snapshot overwrite one another.

3. Hint 3

   get(index, snapId) wants the last change to index recorded with an id <= snapId — binary search that index's list. No such change means the element was still 0.

How to solve Snapshot Array

Record history per element instead of copying the array: each index keeps a list of (snapId, value) pairs, where snapId is the id the next snapshot will get at the time of the write.

Approach

1. Keep a counter snapId = 0 and, for each index, an initially empty history list.
2. set(index, value): if the index's last entry has id snapId, overwrite its value; otherwise append (snapId, value).
3. snap(): return snapId and then increase it.
4. get(index, snapId): binary search the index's history for the last entry with id <= snapId and return its value, or 0 if there is none.

Why it works

A write made while the counter is s happens after snapshot s - 1 and before snapshot s, so it belongs to snapshot s and every later one until the element changes again. Within one id only the last write matters, which the overwrite keeps. The ids in each history are increasing, so the last entry with id <= snapId is the value the element held when that snapshot was taken.

Complexity

• Time — O(1) per set and snap, O(log k) per get for an index changed k times
• Space — O(number of set calls)

Pitfalls

• Copying the array on snap is O(length) per call — 2.5 × 10^9 steps at the limits.
• Appending on every set instead of overwriting within the same id still works for get if the search finds the last matching entry; finding the first one returns a stale value.
• Untouched elements are 0, so an empty history (or one whose first change came later) answers 0.

Reference solution

Python

import bisect

class SnapshotArray:

    def __init__(self, length: int):
        self.snap_id = 0
        self.ids = {}   # index -> snapshot ids of its changes, increasing
        self.vals = {}  # index -> the value written for each of those ids

    def set(self, index: int, value: int) -> None:
        ids = self.ids.setdefault(index, [])
        vals = self.vals.setdefault(index, [])
        if ids and ids[-1] == self.snap_id:
            vals[-1] = value  # a later write before the same snapshot wins
        else:
            ids.append(self.snap_id)
            vals.append(value)

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

    def get(self, index: int, snapId: int) -> int:
        ids = self.ids.get(index)
        if not ids:
            return 0
        i = bisect.bisect_right(ids, snapId) - 1
        return self.vals[index][i] if i >= 0 else 0

Java

class SnapshotArray {
    private int snapId = 0;
    private HashMap<Integer, TreeMap<Integer, Integer>> h = new HashMap<>();

    public SnapshotArray(int length) {
    }

    public void set(int index, int value) {
        // put() on the same snapshot id overwrites the earlier write
        h.computeIfAbsent(index, k -> new TreeMap<>()).put(snapId, value);
    }

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

    public int get(int index, int snapId) {
        TreeMap<Integer, Integer> t = h.get(index);
        if (t == null) return 0;
        Map.Entry<Integer, Integer> e = t.floorEntry(snapId);
        return e == null ? 0 : e.getValue();
    }
}

C++

class SnapshotArray {
    int snapId = 0;
    vector<vector<pair<int, int>>> h; // per index: (snapshot id, value), ids increasing
public:
    SnapshotArray(int length) : h(length) {}

    void set(int index, int value) {
        auto& v = h[index];
        if (!v.empty() && v.back().first == snapId) v.back().second = value; // same snapshot: overwrite
        else v.push_back({snapId, value});
    }

    int snap() {
        return snapId++;
    }

    int get(int index, int snapId) {
        auto& v = h[index];
        auto it = upper_bound(v.begin(), v.end(), make_pair(snapId, INT_MAX));
        return it == v.begin() ? 0 : prev(it)->second;
    }
};

JavaScript

var SnapshotArray = function(length) {
    this.snapId = 0;
    this.h = new Map(); // index -> { ids: [], vals: [] }
};

SnapshotArray.prototype.set = function(index, value) {
    var e = this.h.get(index);
    if (!e) { e = { ids: [], vals: [] }; this.h.set(index, e); }
    var n = e.ids.length;
    if (n > 0 && e.ids[n - 1] === this.snapId) e.vals[n - 1] = value; // same snapshot: overwrite
    else { e.ids.push(this.snapId); e.vals.push(value); }
};

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

SnapshotArray.prototype.get = function(index, snapId) {
    var e = this.h.get(index);
    if (!e) return 0;
    var lo = 0, hi = e.ids.length; // first id > snapId
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (e.ids[mid] <= snapId) lo = mid + 1; else hi = mid;
    }
    return lo > 0 ? e.vals[lo - 1] : 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium