Snapshot Array - Practice Coding Problems

Snapshot Array - Problem

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["SnapshotArray","set","snap","get"], values = [[3],[0,5],[],[0,0]]

› Output: [null,null,0,5]

💡 Note: Create array of length 3 [0,0,0]. Set index 0 to 5 [5,0,0]. Take snapshot (returns 0). Get value at index 0 from snapshot 0 returns 5.

Example 2 — Multiple Snapshots

$ Input: operations = ["SnapshotArray","set","snap","set","snap","get","get"], values = [[2],[1,10],[],[1,20],[],[1,0],[1,1]]

› Output: [null,null,0,null,1,10,20]

💡 Note: Array [0,0] → set(1,10) → [0,10] → snap() returns 0 → set(1,20) → [0,20] → snap() returns 1. get(1,0) returns 10 from snapshot 0, get(1,1) returns 20 from snapshot 1.

Example 3 — No Changes Before Snap

$ Input: operations = ["SnapshotArray","snap","get"], values = [[1],[],[0,0]]

› Output: [null,0,0]

💡 Note: Create array [0], immediately take snapshot (returns 0), get(0,0) returns initial value 0.

Constraints

1 ≤ length ≤ 5 × 10⁴
0 ≤ index < length
0 ≤ val ≤ 10⁹
0 ≤ snap_id < (number of times we call snap())
At most 5 × 10⁴ calls will be made to set, snap, and get.

Visualization

Tap to expand

Understanding the Visualization

Input

Array operations: create, set, snap, get

Process

Track changes with timestamps, not full copies

Output

Return results for each operation

Key Takeaway

🎯 Key Insight: Store only changes with timestamps and use binary search for fast historical lookups

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

The key insight is to store only changes with timestamps instead of full array snapshots. The optimal approach uses a list of (snap_id, value) pairs for each index and binary search for retrieval. Time: O(log s) for get operations, Space: O(changes) instead of O(n × snapshots).

Common Approaches

Approach	Time	Space	Notes
✓ Store Full Array Snapshots	O(n)	O(n × s)	Keep complete array copy for each snapshot
Store Only Changes with Binary Search	O(log s)	O(m)	Track only modified values with snapshot timestamps

Store Full Array Snapshots — Algorithm Steps

Store complete array copy on each snap()
Access snapshot array directly for get()

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Array [0,0,0] created

Set Operation

Change array[0] to 5: [5,0,0]

Snap Operation

Store complete copy [5,0,0] as snapshot 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* array;
    int** snapshots;
    int length;
    int snapId;
    int snapshotCount;
} SnapshotArray;

SnapshotArray* createSnapshotArray(int length) {
    SnapshotArray* obj = malloc(sizeof(SnapshotArray));
    obj->array = calloc(length, sizeof(int));
    obj->snapshots = malloc(1000 * sizeof(int*));
    obj->length = length;
    obj->snapId = 0;
    obj->snapshotCount = 0;
    return obj;
}

void set(SnapshotArray* obj, int index, int val) {
    obj->array[index] = val;
}

int snap(SnapshotArray* obj) {
    obj->snapshots[obj->snapshotCount] = malloc(obj->length * sizeof(int));
    memcpy(obj->snapshots[obj->snapshotCount], obj->array, obj->length * sizeof(int));
    obj->snapshotCount++;
    return obj->snapId++;
}

int get(SnapshotArray* obj, int index, int snapId) {
    return obj->snapshots[snapId][index];
}

int main() {
    // Simplified implementation for demo
    SnapshotArray* obj = createSnapshotArray(3);
    printf("[null,");
    set(obj, 0, 5);
    printf("null,");
    int snapResult = snap(obj);
    printf("%d,", snapResult);
    int getResult = get(obj, 0, 0);
    printf("%d]\n", getResult);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

snap() copies entire array of size n

✓ Linear Growth

Space Complexity

O(n × s)

Store s snapshots, each of size n

⚡ Linearithmic Space

124.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Store Full Array Snapshots — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler