Snapshot Array

MediumDesign · Binary Search🧩 Data Structure Design LeetCode #1146 ↗Updated Oct 30, 2026

Problem

Design a SnapshotArray(length) whose cells all start at 0. set(index, val) writes a cell, snap() freezes the current contents and returns a snapshot id (0, 1, 2, …), and get(index, snapId) returns what that cell held when snapshot snapId was taken.

InputSnapshotArray(3); set(0,5); snap(); set(0,6); get(0,0)Outputsnap() = 0, get = 5

InputSnapshotArray(2); snap(); snap(); set(1,4); snap(); get(1,1); get(1,2)Output0, 1, 2, then 0, 4

1 ≤ length ≤ 5·10⁴ · 0 ≤ val ≤ 10⁹ · snapId < number of snap() calls · ≤ 5·10⁴ calls in total

Try it yourself

Java

class SnapshotArray {
    public SnapshotArray(int length) {
        
    }

    public void set(int index, int val) {
        
    }

    public int snap() {
        
    }

    public int get(int index, int snap_id) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Don’t copy the array per snapshot — record only changes. Each cell keeps a history of (snapId, value) pairs in increasing snapId order; get is then “last change with snapId ≤ asked id”, a binary search.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceFull Copy per Snapshot

Time snap O(length), set/get O(1)Space O(length · snaps)

Keep the live array and, on every snap(), store a complete copy of it. Reading an old snapshot is then a plain array access.

Java

class SnapshotArray {
    private final int[] current;
    private final List<int[]> snaps = new ArrayList<>();
    public SnapshotArray(int length) { current = new int[length]; }
    public void set(int index, int val) { current[index] = val; }
    public int snap() {
        snaps.add(current.clone()); // freeze a full copy
        return snaps.size() - 1;
    }
    public int get(int index, int snap_id) { return snaps.get(snap_id)[index]; }
}

Fast reads, but 5·10⁴ snaps of a 5·10⁴-cell array is billions of ints.

BetterPer-Snapshot Change Maps + Backward Scan

Time set/snap O(1), get O(snaps)Space O(sets)

Store only the cells written between two snaps, as one small map per snapshot. The value of a cell at snapshot s is its most recent change in snapshots s, s-1, …, 0; if it was never written, it is still 0.

Java

class SnapshotArray {
    private final List<Map<Integer, Integer>> diffs = new ArrayList<>();
    private Map<Integer, Integer> pending = new HashMap<>(); // writes since the last snap
    public SnapshotArray(int length) { }
    public void set(int index, int val) { pending.put(index, val); }
    public int snap() {
        diffs.add(pending);
        pending = new HashMap<>();
        return diffs.size() - 1;
    }
    public int get(int index, int snap_id) {
        for (int s = snap_id; s >= 0; s--) { // newest change at or before snap_id wins
            Integer v = diffs.get(s).get(index);
            if (v != null) return v;
        }
        return 0; // never written
    }
}

Memory proportional to writes, but a rarely-written cell makes get walk every snapshot.

OptimalPer-Cell History + Binary Search

Time set/snap O(1), get O(log h)Space O(length + sets)

Flip the layout: each cell owns a list of (snapId, value) pairs, seeded with (0, 0). Writes inside the same snapshot overwrite the last pair; otherwise a new pair is appended, so ids stay sorted. get binary searches for the last pair with id ≤ snap_id (h = that cell’s history length).

Java

class SnapshotArray {
    // history.get(i) = (snapId, value) pairs for cell i, snapId ascending
    private final List<List<int[]>> history = new ArrayList<>();
    private int snapId = 0;
    public SnapshotArray(int length) {
        for (int i = 0; i < length; i++) {
            List<int[]> h = new ArrayList<>();
            h.add(new int[]{0, 0}); // every cell starts as 0
            history.add(h);
        }
    }
    public void set(int index, int val) {
        List<int[]> h = history.get(index);
        int[] last = h.get(h.size() - 1);
        if (last[0] == snapId) last[1] = val; // rewrite within the same snapshot
        else h.add(new int[]{snapId, val});
    }
    public int snap() { return snapId++; }
    public int get(int index, int snap_id) {
        List<int[]> h = history.get(index);
        int lo = 0, hi = h.size() - 1; // last pair with id <= snap_id
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (h.get(mid)[0] <= snap_id) lo = mid;
            else hi = mid - 1;
        }
        return h.get(lo)[1];
    }
}

Only changes are stored and every operation is O(1) or O(log h) — the expected design.

Pro tip

A TreeMap<Integer,Integer> per cell with floorEntry(snap_id) is an equally valid, shorter answer.

At a glance

Level	Approach	Time	Space
Brute Force	Full Copy per Snapshot	`snap O(length), set/get O(1)`	`O(length · snaps)`
Better	Per-Snapshot Change Maps + Backward Scan	`set/snap O(1), get O(snaps)`	`O(sets)`
Optimal	Per-Cell History + Binary Search	`set/snap O(1), get O(log h)`	`O(length + sets)`

Common pitfalls

Copying the whole array on snap() — blows memory with many snapshots.
Appending a new pair for every write in the same snapshot — history grows without need.
Off-by-one in ids: snap() returns the id before incrementing.

Interview tips

Start from the full-copy idea, then ask “what actually changes between snaps?”
Point out the history is sorted for free because snapshot ids only grow.
Compare per-snapshot vs. per-cell storage: the second makes reads logarithmic.

Pattern

Versioned storage + floor search → reading old states of data that changes over time.

My notes saved in this browser