Snapshot Array

medium design binary search

Problem

Design an array of length n initialized to 0, with operations: set(index, val), snap() returning a snap_id, and get(index, snap_id) returning the value at that index when snap_id was taken.

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

Output5

snap 0 captured index 0 = 5; later writes don't change snap 0.

length

ops (e.g. set 0 5; snap; set 0 6; get 0 0)

from bisect import bisect_right
class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0
        self.h = [[(-1, 0)] for _ in range(length)]
    def set(self, index, val):
        self.h[index].append((self.snap_id, val))
    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1
    def get(self, index, snap_id):
        col = self.h[index]
        i = bisect_right(col, (snap_id, float('inf'))) - 1
        return col[i][1]

class SnapshotArray {
  constructor(length) {
    this.snapId = 0;
    this.h = Array.from({length}, () => [[-1, 0]]);
  }
  set(index, val) {
    this.h[index].push([this.snapId, val]);
  }
  snap() { return this.snapId++; }
  get(index, snapId) {
    const col = this.h[index];
    let lo = 0, hi = col.length - 1, ans = 0;
    while (lo <= hi) {
      const m = (lo + hi) >> 1;
      if (col[m][0] <= snapId) { ans = col[m][1]; lo = m + 1; }
      else hi = m - 1;
    }
    return ans;
  }
}

class SnapshotArray {
    int snapId = 0;
    List<List<int[]>> h;
    public SnapshotArray(int length) {
        h = new ArrayList<>();
        for (int i = 0; i < length; i++) { List<int[]> col = new ArrayList<>(); col.add(new int[]{-1, 0}); h.add(col); }
    }
    public void set(int index, int val) { h.get(index).add(new int[]{snapId, val}); }
    public int snap() { return snapId++; }
    public int get(int index, int snapId) {
        List<int[]> col = h.get(index);
        int lo = 0, hi = col.size() - 1, ans = 0;
        while (lo <= hi) {
            int m = (lo + hi) >>> 1;
            if (col.get(m)[0] <= snapId) { ans = col.get(m)[1]; lo = m + 1; } else hi = m - 1;
        }
        return ans;
    }
}

class SnapshotArray {
public:
    int snapId = 0;
    vector<vector<pair<int,int>>> h;
    SnapshotArray(int length) : h(length, {{-1, 0}}) {}
    void set(int index, int val) { h[index].push_back({snapId, val}); }
    int snap() { return snapId++; }
    int get(int index, int sid) {
        auto& col = h[index];
        int lo = 0, hi = (int)col.size() - 1, ans = 0;
        while (lo <= hi) {
            int m = (lo + hi) / 2;
            if (col[m].first <= sid) { ans = col[m].second; lo = m + 1; }
            else hi = m - 1;
        }
        return ans;
    }
};

Explanation

A naive design would copy the whole array on every snap(), which is wasteful when most values never change. The smart approach stores, for each index, only a history of changes tagged with the snap id at which they happened.

Each index keeps a list of (snap_id, value) pairs, starting with (-1, 0). A set simply appends (current snap_id, val) to that index's list. A snap() just bumps a global counter and returns the previous id — no copying at all.

The clever part is get(index, snap_id). Since each index's list is naturally sorted by snap id, we binary search for the last entry whose recorded snap id is <= snap_id. That entry holds the value that was in effect at the moment that snapshot was taken.

Example: set(0, 5), then snap() returns 0, then set(0, 6). Now get(0, 0) binary searches index 0's history for the newest entry with snap id <= 0, which is (0, 5), so it returns 5 — the later write of 6 does not affect the older snapshot.

Reads cost only O(log Q) for Q total writes, and the structure uses space proportional to the number of actual changes rather than snapshots times length.

Time: O(log Q) per get Space: O(n + Q)