Snapshot Array Solution in C++

Problem Description

Ah, the Snapshot Array! It’s like a time machine for your data, but instead of traveling back to the Jurassic period, you’re just trying to remember what your array looked like a few moments ago. Imagine you’re a forgetful chef who keeps changing the recipe but wants to remember what the dish tasted like at different stages. You can set values, take snapshots, and retrieve the values from those snapshots. It’s like having a photo album for your array, but instead of pictures, you have numbers.

In this problem, you’ll be tasked with creating a data structure that allows you to:

Set a value at a specific index.
Take a snapshot of the current state of the array.
Retrieve the value at a specific index from a specific snapshot.

Code Solution


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>& snap = snaps[index];
    auto it = ranges::lower_bound(snap, make_pair(snap_id + 1, 0));
    return prev(it)->second;
  }

 private:
  vector>> snaps;
  int snap_id = 0;
};

Approach

The approach here is quite straightforward. We maintain a vector of vectors, where each inner vector holds pairs of snapshot IDs and their corresponding values. When you set a value, we check if it’s the same snapshot as the last one. If it is, we simply update the value. If not, we create a new entry for that snapshot. When you take a snapshot, we just increment the snapshot ID. To retrieve a value, we use binary search to find the most recent value before the requested snapshot ID.

Time and Space Complexity

Operation	Time Complexity	Space Complexity
set	O(1)	O(n * m)
snap	O(1)
get	O(log n)

Real-World Example

Imagine you’re a social media influencer who keeps changing your profile picture. You want to keep track of how your profile looked at different times. Each time you change your picture, you take a snapshot. Later, if someone asks you what your profile looked like last month, you can just pull up that snapshot and show them! This is essentially what the Snapshot Array does, but instead of pictures, it’s handling numbers.