1146. Snapshot Array - Detailed Explanation

Problem Statement

Implement a data structure called SnapshotArray that supports the following operations:

• SnapshotArray(int length): Initializes an array-like data structure of the given length with all elements initialized to 0.

• void set(int index, int val): Sets the element at the specified index to be equal to val.

• int snap(): Takes a snapshot of the array and returns the snapshot id (the number of times snap() has been called minus one).

• int get(int index, int snap_id): Returns the value at the specified index at the time the snapshot with id snap_id was taken.

Example 1

• Input:
  • Commands: ["SnapshotArray", "set", "snap", "set", "get"]
  • Arguments: [[3], [0,5], [], [0,6], [0,0]]
• Output: [null, null, 0, null, 5]
• Explanation:

  1. Initialize a SnapshotArray of length 3: [0, 0, 0].

  2. Call set(0, 5): Array becomes [5, 0, 0].

  3. Call snap(): Takes a snapshot and returns snap id 0.

  4. Call set(0, 6): Array becomes [6, 0, 0].

  5. Call get(0, 0): Returns the value at index 0 from snapshot 0, which is 5.

Example 2

• Input:
  • Commands: ["SnapshotArray", "set", "set", "snap", "set", "get"]
  • Arguments: [[1], [0,15], [0,20], [], [0,25], [0,0]]
• Output: [null, null, null, 0, null, 20]
• Explanation:

  1. Initialize a SnapshotArray of length 1: [0].

  2. Call set(0, 15): Array becomes [15].

  3. Call set(0, 20): Array becomes [20].

  4. Call snap(): Takes a snapshot and returns snap id 0.

  5. Call set(0, 25): Array becomes [25].

  6. Call get(0, 0): Returns the value at index 0 from snapshot 0, which is 20.

Example 3

• Input:
  • Commands: ["SnapshotArray", "snap", "get", "set", "snap", "get"]
  • Arguments: [[2], [], [1,0], [1,5], [], [1,1]]
• Output: [null, 0, 0, null, 1, 5]
• Explanation:

  1. Initialize a SnapshotArray of length 2: [0, 0].

  2. Call snap(): Takes a snapshot and returns snap id 0.

  3. Call get(1, 0): Returns the value at index 1 from snapshot 0, which is 0.

  4. Call set(1, 5): Array becomes [0, 5].

  5. Call snap(): Takes another snapshot and returns snap id 1.

  6. Call get(1, 1): Returns the value at index 1 from snapshot 1, which is 5.

Constraints

• 1 <= length <= 50,000
• 0 <= index < length
• 0 <= val <= 10⁹
• At most 50,000 calls will be made to set, snap, and get.

Hints to Approach the Problem

• Hint 1:
  Think about how you might avoid copying the entire array every time a snapshot is taken. Is there a way to record only the changes (updates) instead of saving the whole state?

• Hint 2:
  For each index, you could maintain a history of changes (each with the snapshot id and value). Then, when you call get(index, snap_id), you only need to find the most recent update that occurred on or before that snapshot id. How might you efficiently search through these changes?

A. Brute Force Approach

Explanation

• Idea:
  Every time a snap() is called, copy the entire array and store it. For a get(index, snap_id), simply look up the value in the stored snapshot.

• Pros:
  Easy to understand and implement.

• Cons:

  • Memory inefficient: If there are many snapshots and a large array, storing each full snapshot leads to high space usage.
  • Time inefficient: Taking a snapshot is O(n) where n is the length of the array.

Visual Example

Imagine an array of length 3:

• Start: [0, 0, 0]
• After set(0, 5): [5, 0, 0]
• Snapshot taken → copy [5, 0, 0]
• After set(0, 6): [6, 0, 0]
• To answer get(0, snap_id=0), retrieve the value from the stored snapshot: 5.

B. Optimal Approach: Using History with Binary Search

Explanation

• Idea:
  Instead of copying the entire array, store for each index only the changes.
  For each index, maintain a list of (snap_id, value) pairs.

  • set(index, val): Update the current snapshot’s value for the given index.
  • snap(): Increment the current snapshot id and return the previous id.
  • get(index, snap_id): Use binary search to quickly find the latest change for the index that is less than or equal to the given snap_id.

• Advantages:

  • Memory efficient: Only changes are stored.
  • Time efficient: get is O(log m) per call (where m is the number of changes at that index).

Visual Example

Consider an index that initially has a history: [(0, 0)] (value 0 at snapshot 0).

• After set(index, 5) before any snapshot, update to [(0, 0), (current_snap, 5)].

• When snap() is called, the current snapshot id (say 0) is fixed.

• If later set(index, 6) is called in the new snapshot, append a new record.

• To get the value for a previous snapshot, binary search finds the most recent pair with a snap_id less than or equal to the query.

Python Implementation