Command Palette

Search for a command to run...

Hectal
Problem 40.4 · Designing Data StructuresMedium

Snapshot Array

PatternCombine Structures to DesignBinary Search on an Index

What it teaches: Store only changes per index, tagged with the snapshot id; answer with a floor lookup.

Practise it on judges as “Snapshot Array”.

In plain words

Think of a row of boxes holding numbers, and a camera. Taking a photo (snap) gives it a number 0, 1, 2 … Later you ask "what was in box 0 in photo 0?" Copying the whole row for every photo is wasteful, so each box keeps only its own small diary of changes: "from photo k, my value is v". To answer, find the last diary entry at or before the photo number.

Return the snapshot id from snap and the old value from get. Example: SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0) → 0, 5.

The problem

Design SnapshotArray(length) (all zeros) with set(index, val), snap() returning the snapshot id (0, 1, …), and get(index, snapId) returning the value at that snapshot.

Example 1

Input: SnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)
Output: 0, 5

Constraints

  • Up to 5 × 10⁴ calls

Pattern clues in the wording

  • → Versions of a whole array
  • → Copying the array per snapshot is too slow

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

SnapshotArray · starter
import java.util.*;

class SnapshotArray {
    public SnapshotArray(int length) {}
    public void set(int index, int val) {}
    public int snap() { return 0; }
    public int get(int index, int snapId) { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
ops = ["SnapshotArray","set","snap","set","get"]
args = [[3],[0,5],[],[0,6],[0,0]]
[null,null,0,null,5]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. TreeMap per index · O(log s) set/get, O(1) snap
1

TreeMap per index

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

history[i] maps snap id → value (starting with 0 → 0). set writes at the current snap id; snap returns id++; get floors.

▶ Dry run: One small history per indexSnapshotArray(3); set(0, 5); snap(); set(0, 6); get(0, 0)

history(map)

index 0: {0: 0}index 1: {0: 0}index 2: {0: 0}

state(vars)

snapId: 0

Step 1/5Start: every index has one entry, value 0 from snapshot 0.

Approach 1
import java.util.*;

class SnapshotArray {
    private final List<TreeMap<Integer, Integer>> history = new ArrayList<>();
    private int snapId = 0;

    public SnapshotArray(int length) {
        for (int i = 0; i < length; i++) {
            TreeMap<Integer, Integer> m = new TreeMap<>();
            m.put(0, 0);
            history.add(m);
        }
    }

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

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

    public int get(int index, int snapId) { return history.get(index).floorEntry(snapId).getValue(); }
}

Verdict: Memory proportional to changes, not snapshots × length.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Several sets before one snap (last wins)
  • get on an index never set (0)

Mistakes people make

  • Copying the whole array on every snap.

Interview

Follow-up questions

How do databases do the same thing?