Snapshot Array

mediumAmazon-tagged: Design-style coding47 stepsJava · Python · C++

An array that can take snapshots and read any index as of any snapshot. Copying the array on every snap is too slow. Instead, each index keeps a list of (snapId, value) changes; get binary-searches for the last change made at or before the requested snapshot.

▶ Watch the animated trace

Traced input: SnapshotArray(3): set(0, 5), snap(), set(0, 6), get(0, 0), snap(), get(0, 1), get(2, 1) → [null, null, 0, null, 5, 1, 6, 0]. Original problem: leetcode.com/problems/snapshot-array/

Complexity

BestO(1)

AverageO(log s)

WorstO(log s)

SpaceO(n + sets)

set and snap are O(1); get is a binary search over that index's history.

Key idea

Only store values that changed, tagged with the current snapshot id.
Several sets between snaps overwrite the same (snapId, value) entry.
get(index, id) = last entry with snapId ≤ id.

Common mistakes

Copying the whole array on snap: O(n) per snap.
Off-by-one: snap returns the id of the snapshot just taken, then the counter increments.

Solution

Java

class SnapshotArray {
    private final List<int[]>[] history;
    private int snapId = 0;

    SnapshotArray(int length) {
        history = new List[length];
        for (int i = 0; i < length; i++) {
            history[i] = new ArrayList<>();
            history[i].add(new int[]{0, 0});
        }
    }

    void set(int index, int val) {
        List<int[]> h = history[index];
        if (h.get(h.size() - 1)[0] == snapId) h.get(h.size() - 1)[1] = val;
        else h.add(new int[]{snapId, val});
    }

    int snap() {
        return snapId++;
    }

    int get(int index, int id) {
        List<int[]> h = history[index];
        int lo = 0, hi = h.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (h.get(mid)[0] <= id) lo = mid;
            else hi = mid - 1;
        }
        return h.get(lo)[1];
    }
}

Python

class SnapshotArray:
    def __init__(self, length: int):
        self.history = [[(0, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        h = self.history[index]
        if h[-1][0] == self.snap_id: h[-1] = (self.snap_id, val)
        else: h.append((self.snap_id, val))

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

    def get(self, index: int, snap_id: int) -> int:
        h = self.history[index]
        i = bisect.bisect_right(h, (snap_id, float("inf"))) - 1
        return h[i][1]

C++

class SnapshotArray {
    vector<vector<pair<int, int>>> history;
    int snapId = 0;

public:
    SnapshotArray(int length) : history(length, {{0, 0}}) {}

    void set(int index, int val) {
        auto& h = history[index];
        if (h.back().first == snapId) h.back().second = val;
        else h.push_back({snapId, val});
    }

    int snap() {
        return snapId++;
    }

    int get(int index, int id) {
        auto& h = history[index];
        auto it = upper_bound(h.begin(), h.end(), make_pair(id, INT_MAX));
        return prev(it)->second;
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Several sets before a snap The last value before the snap wins.	`SnapshotArray(1): set(0, 1), set(0, 2), snap(), get(0, 0)`	`[null, null, null, 0, 2]`
Never set Untouched indices read as 0.	`SnapshotArray(2): snap(), get(1, 0)`	`[null, 0, 0]`