Snapshot Array

Medium Binary Search Basics Original on LeetCode

Snapshot Array is a medium binary search problem solved with the basics pattern. The best approach, optimal (per-index change history + binary search), runs in O(1) for set and snap, O(log k) for get time and O(length + sets) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy the array on every snap) up.

Problem

Design SnapshotArray, an array of length integers (all starting at 0) that can take snapshots of its contents.

  • set(index, val) writes val at position index.
  • snap() takes a snapshot and returns its id: the first call returns 0, the next 1, and so on.
  • get(index, snap_id) returns the value that position index held at the moment snapshot snap_id was taken.

Many snapshots may be taken while only a few positions change, so avoid copying the whole array each time.

Examples

Example 1

Input
SnapshotArray(4), set(1, 8), snap(), set(1, 3), set(2, 6), get(1, 0), snap(), get(1, 1), get(2, 0)
Output
null, null, 0, null, null, 8, 1, 3, 0
Why
Snapshot 0 saw index 1 = 8. Snapshot 1 saw index 1 = 3 and index 2 = 6, but index 2 was still 0 at snapshot 0.

Example 2

Input
SnapshotArray(2), snap(), snap(), set(0, 5), get(0, 1), snap(), get(0, 2)
Output
null, 0, 1, null, 0, 2, 5
Why
The value 5 was written after snapshots 0 and 1, so only snapshot 2 sees it.

Constraints

  • 1 <= length <= 5 * 10^4
  • 0 <= index < length, 0 <= val <= 10^9
  • 0 <= snap_id < the number of snap() calls made so far.
  • At most 5 * 10^4 calls to set, snap and get in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (copy the array on every snap)O(length) per snap, O(1) per set and getO(length · snaps)
Optimal (per-index change history + binary search)O(1) for set and snap, O(log k) for getO(length + sets)

1Brute force (copy the array on every snap)

TimeO(length) per snap, O(1) per set and getEach snapshot copies the whole array.
SpaceO(length · snaps)Every snapshot keeps a full copy, even if nothing changed.

Keep the live array and a list of full copies. snap() appends a copy of the live array; get reads from the requested copy.

  1. set(index, val): cur[index] = val.
  2. snap(): append a copy of cur to snaps and return its position.
  3. get(index, snap_id): return snaps[snap_id][index].
class SnapshotArray {
    private final int[] cur;
    private final List<int[]> snaps = new ArrayList<>();

    public SnapshotArray(int length) {
        cur = new int[length];
    }

    public void set(int index, int val) {
        cur[index] = val;
    }

    public int snap() {
        snaps.add(cur.clone());
        return snaps.size() - 1;
    }

    public int get(int index, int snap_id) {
        return snaps.get(snap_id)[index];
    }
}

Edge cases to test

  • get on an index that was never set returns 0
  • Several sets on the same index between two snapshots: only the last one counts
  • Many snapshots with no sets in between
  • A set after the latest snapshot must not change what older snapshots return

Hints

Hint 1

Copying the whole array on every snap is correct, but how much memory do 5 · 10^4 snapshots of 5 · 10^4 values take?

Hint 2

Most snapshots differ from the previous one in very few positions. Store, per index, only the moments its value changed.

Hint 3

For index i keep a list of (snapId, value) pairs in increasing snapId order. get(i, s) is the last pair with snapId <= s: a binary search.

FAQ

What is the best time complexity for Snapshot Array?

Optimal (per-index change history + binary search) runs in O(1) for set and snap, O(log k) for get time and O(length + sets) extra space. get searches the k changes recorded for one index.

Which pattern does Snapshot Array use?

It is a binary search problem that uses the basics pattern. Other problems with the same pattern: Fundamentals, Binary Search, Time Based Key-Value Store.

Is there a brute force solution for Snapshot Array?

Yes. Brute force (copy the array on every snap) takes O(length) per snap, O(1) per set and get time and O(length · snaps) space. Keep the live array and a list of full copies.

Which edge cases should I test for Snapshot Array?

get on an index that was never set returns 0; Several sets on the same index between two snapshots: only the last one counts; Many snapshots with no sets in between; A set after the latest snapshot must not change what older snapshots return.