1146. Snapshot Array LeetCode Solution

In this guide, you will get 1146. Snapshot Array LeetCode Solution with the best time and space complexity. The solution to Snapshot Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Snapshot Array solution in C++
Snapshot Array solution in Java
Snapshot Array solution in Python
Additional Resources

1146. Snapshot Array LeetCode Solution image

Problem Statement of Snapshot Array

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

Example 1:

Input: [“SnapshotArray”,”set”,”snap”,”set”,”get”]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5

Constraints:

1 <= length <= 5 * 104
0 <= index < length
0 <= val <= 109
0 <= snap_id < (the total number of times we call snap())
At most 5 * 104 calls will be made to set, snap, and get.

Complexity Analysis

Time Complexity: O(\log |\texttt{set()}|)
Space Complexity: O(|\texttt{set()}|)

1146. Snapshot Array LeetCode Solution in C++

class SnapshotArray {
 public:
  SnapshotArray(int length) : snaps(length) {
    for (auto& snap : snaps)
      snap.emplace_back(0, 0);
  }

  void set(int index, int val) {
    auto& [lastSnapId, lastVal] = snaps[index].back();
    if (lastSnapId == snap_id)
      lastVal = val;
    else
      snaps[index].emplace_back(snap_id, val);
  }

  int snap() {
    return snap_id++;
  }

  int get(int index, int snap_id) {
    const vector<pair<int, int>>& snap = snaps[index];
    auto it = ranges::lower_bound(snap, make_pair(snap_id + 1, 0));
    return prev(it)->second;
  }

 private:
  // snaps[i] := [(snap_id, val)]
  vector<vector<pair<int, int>>> snaps;
  int snap_id = 0;
};
/* code provided by PROGIEZ */

1146. Snapshot Array LeetCode Solution in Java

class SnapshotArray {
  public SnapshotArray(int length) {
    snaps = new List[length];
    for (int i = 0; i < length; ++i) {
      snaps[i] = new ArrayList<>();
      snaps[i].add(new int[] {0, 0});
    }
  }

  public void set(int index, int val) {
    int[] snap = snaps[index].get(snaps[index].size() - 1);
    if (snap[0] == snap_id)
      snap[1] = val;
    else
      snaps[index].add(new int[] {snap_id, val});
  }

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

  public int get(int index, int snap_id) {
    int i = Collections.binarySearch(snaps[index], new int[] {snap_id, 0},
                                     (a, b) -> Integer.compare(a[0], b[0]));
    if (i < 0)
      i = -i - 2;
    return snaps[index].get(i)[1];
  }

  private List<int[]>[] snaps;
  private int snap_id = 0;
}
// code provided by PROGIEZ

1146. Snapshot Array LeetCode Solution in Python

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:
    snap = self.snaps[index][-1]
    if snap[0] == self.snap_id:
      snap[1] = val
    else:
      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_left(self.snaps[index], [snap_id + 1]) - 1
    return self.snaps[index][i][1]
 # code by PROGIEZ