Snapshot Array Solution in Java

Problem Description

Ah, the Snapshot Array problem! Imagine you’re trying to keep track of your ever-changing mood throughout the day. One moment you’re happy, the next you’re grumpy because someone stole your fries. Wouldn’t it be great if you could take a snapshot of your mood at different times? Well, that’s exactly what this problem is about!

In the world of programming, a Snapshot Array allows you to store values at different “snapshots” in time. You can set values, take snapshots, and retrieve values from those snapshots. It’s like having a time machine, but instead of traveling through time, you’re just traveling through your array!

Code Solution


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[] snaps;
  private int snap_id = 0;
}

Approach

The approach taken in this solution is quite straightforward. We maintain a list of snapshots for each index in the array. When you set a value, it checks if the current snapshot ID matches the last one. If it does, it updates the value; if not, it creates a new snapshot. The snap() method simply increments the snapshot ID, and the get() method retrieves the value from the closest snapshot that is less than or equal to the requested snapshot ID.

Time and Space Complexity

Operation	Time Complexity	Space Complexity
set()	O(1) on average, O(n) in the worst case	O(n * m)
snap()	O(1)
get()	O(log n)

Real-World Example

Think of a photo album where you take pictures of your family at different events. Each event is like a snapshot, and you can look back at any event to see how everyone looked at that time. Similarly, the Snapshot Array allows you to “look back” at the values stored at different times, making it a powerful tool for tracking changes over time.