Skip to content

1146. Snapshot Array 👍

  • Time: Constructor: $O(\texttt{length})$, set(): $O(\log \texttt{S})$ (C++/Java), $O(1)$ (Python), snap(): $O(1)$, get(): $O(\log |\texttt{snap()}|)$
  • Space: $O(|\texttt{snap()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class SnapshotArray {
 public:
  SnapshotArray(int length) : snaps(length) {
    for (auto& snap : snaps)
      snap[0] = 0;
  }

  void set(int index, int val) {
    snaps[index][snap_id] = val;
  }

  int snap() {
    return snap_id++;
  }

  int get(int index, int snap_id) {
    auto it = snaps[index].upper_bound(snap_id);
    return prev(it)->second;
  }

 private:
  vector<map<int, int>> snaps;
  int snap_id = 0;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class SnapshotArray {
  public SnapshotArray(int length) {
    snaps = new TreeMap[length];
    for (int i = 0; i < length; ++i) {
      snaps[i] = new TreeMap<>();
      snaps[i].put(0, 0);
    }
  }

  public void set(int index, int val) {
    snaps[index].put(snap_id, val);
  }

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

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

  private TreeMap<Integer, Integer>[] snaps;
  private int snap_id = 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class SnapshotArray:
  def __init__(self, length: int):
    self.snaps = [[[0, 0]] for _ in range(length)]
    self.snap_id = 0

  def set(self, index: int, val: int) -> None:
    self.snaps[index].append([self.snap_id, val])

  def snap(self) -> int:
    self.snap_id += 1
    return self.snap_id - 1

  def get(self, index: int, snap_id: int) -> int:
    i = bisect.bisect(self.snaps[index], [snap_id + 1]) - 1
    return self.snaps[index][i][1]
Back to top