Snapshot array

Array Hash Table Binary Search Design

36.7% acceptance

Feb 22, 2026

3914

537

Implement a SnapshotArray that supports the following interface: SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0. void set(index, val) sets the element at the given index to be equal to val. int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1. int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

pub struct SnapshotArray {
  data: Vec<Vec<(i32, i32)>>, // data[index] = sorted list of (snap_id, value)
  snap_id: i32,
}

impl SnapshotArray {
  pub fn new(length: i32) -> Self {
    SnapshotArray {
      data: vec![vec![(0, 0)]; length as usize],
      snap_id: 0,
    }
  }

  pub fn set(&mut self, index: i32, val: i32) {
    let idx = index as usize;
    let sid = self.snap_id;
    if let Some(last) = self.data[idx].last_mut() {
      if last.0 == sid {
        last.1 = val;
        return;
      }
    }
    self.data[idx].push((sid, val));
  }

  pub fn snap(&mut self) -> i32 {
    let id = self.snap_id;
    self.snap_id += 1;
    id
  }

  pub fn get(&self, index: i32, snap_id: i32) -> i32 {
    let arr = &self.data[index as usize];
    let pos = arr.partition_point(|&(s, _)| s <= snap_id);
    if pos == 0 { 0 } else { arr[pos - 1].1 }
  }
}