Snapshot Array
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)writesvalat positionindex.snap()takes a snapshot and returns its id: the first call returns0, the next1, and so on.get(index, snap_id)returns the value that positionindexheld at the moment snapshotsnap_idwas 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^40 <= index < length,0 <= val <= 10^90 <= snap_id <the number ofsnap()calls made so far.- At most
5 * 10^4calls toset,snapandgetin 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy the array on every snap) | O(length) per snap, O(1) per set and get | O(length · snaps) |
| Optimal (per-index change history + binary search) | O(1) for set and snap, O(log k) for get | O(length + sets) |
1Brute force (copy the array on every snap)
O(length) per snap, O(1) per set and getEach snapshot copies the whole array.O(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.
- set(index, val): cur[index] = val.
- snap(): append a copy of cur to snaps and return its position.
- 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];
}
}class SnapshotArray:
def __init__(self, length: int):
self.cur = [0] * length
self.snaps = []
def set(self, index: int, val: int) -> None:
self.cur[index] = val
def snap(self) -> int:
self.snaps.append(self.cur[:])
return len(self.snaps) - 1
def get(self, index: int, snap_id: int) -> int:
return self.snaps[snap_id][index]class SnapshotArray {
vector<int> cur;
vector<vector<int>> snaps;
public:
SnapshotArray(int length) : cur(length, 0) {}
void set(int index, int val) {
cur[index] = val;
}
int snap() {
snaps.push_back(cur);
return snaps.size() - 1;
}
int get(int index, int snap_id) {
return snaps[snap_id][index];
}
};class SnapshotArray {
constructor(length) {
this.cur = new Array(length).fill(0);
this.snaps = [];
}
set(index, val) {
this.cur[index] = val;
}
snap() {
this.snaps.push(this.cur.slice());
return this.snaps.length - 1;
}
get(index, snap_id) {
return this.snaps[snap_id][index];
}
}2Optimal (per-index change history + binary search)
O(1) for set and snap, O(log k) for getget searches the k changes recorded for one index.O(length + sets)One list per index plus one pair per recorded change.For each index store only its changes as (snapId, value) pairs, where snapId is the id the next snap() will return. The pairs are appended in increasing snapId order, so get(index, s) binary-searches for the last change with snapId <= s. A second set in the same snapshot period overwrites the last pair instead of adding one.
- Keep snapId = 0 and, for every index, an empty list of (snapId, value) pairs.
- set(index, val): if the last pair of that index has the current snapId, overwrite its value; otherwise append (snapId, val).
- snap(): return snapId, then increase it by one.
- get(index, s): binary-search the last pair with snapId <= s; return its value, or 0 if there is none.
class SnapshotArray {
private final List<List<int[]>> history = new ArrayList<>();
private int snapId = 0;
public SnapshotArray(int length) {
for (int i = 0; i < length; i++) history.add(new ArrayList<>());
}
public void set(int index, int val) {
List<int[]> h = history.get(index);
if (!h.isEmpty() && h.get(h.size() - 1)[0] == snapId) {
h.get(h.size() - 1)[1] = val;
} 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, found = -1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (h.get(mid)[0] <= snap_id) {
found = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return found < 0 ? 0 : h.get(found)[1];
}
}class SnapshotArray:
def __init__(self, length: int):
self.ids = [[] for _ in range(length)]
self.vals = [[] for _ in range(length)]
self.snap_id = 0
def set(self, index: int, val: int) -> None:
ids, vals = self.ids[index], self.vals[index]
if ids and ids[-1] == self.snap_id:
vals[-1] = val
else:
ids.append(self.snap_id)
vals.append(val)
def snap(self) -> int:
self.snap_id += 1
return self.snap_id - 1
def get(self, index: int, snap_id: int) -> int:
pos = bisect.bisect_right(self.ids[index], snap_id) - 1
return 0 if pos < 0 else self.vals[index][pos]class SnapshotArray {
vector<vector<pair<int, int>>> history;
int snapId = 0;
public:
SnapshotArray(int length) : history(length) {}
void set(int index, int val) {
auto& h = history[index];
if (!h.empty() && h.back().first == snapId) {
h.back().second = val;
} else {
h.push_back({snapId, val});
}
}
int snap() {
return snapId++;
}
int get(int index, int snap_id) {
const auto& h = history[index];
int lo = 0, hi = (int) h.size() - 1, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (h[mid].first <= snap_id) {
found = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return found < 0 ? 0 : h[found].second;
}
};class SnapshotArray {
constructor(length) {
this.history = Array.from({ length }, () => []);
this.snapId = 0;
}
set(index, val) {
const h = this.history[index];
if (h.length > 0 && h[h.length - 1][0] === this.snapId) {
h[h.length - 1][1] = val;
} else {
h.push([this.snapId, val]);
}
}
snap() {
return this.snapId++;
}
get(index, snap_id) {
const h = this.history[index];
let lo = 0, hi = h.length - 1, found = -1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (h[mid][0] <= snap_id) {
found = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return found < 0 ? 0 : h[found][1];
}
}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.