LeetCode //C - 1146. Snapshot Array

1146. 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\ast 10^4$
• 0 <= index < length
• $0<=val<=10^9$
  -0 <= snap_id < (the total number of times we call snap())
• At most $5\ast 10^4$ calls will be made to set, snap, and get.

From: LeetCode
Link: 1146. Snapshot Array

Solution:

Ideas:

1. Snapshot Functionality: The ability to take a snapshot of the array at any point in time and later retrieve the value of any element as it was at the time of any given snapshot.

2. Efficiency in Space: Instead of copying the entire array every time a snapshot is taken (which would be very space-inefficient for large arrays or a high number of snapshots), the implementation stores changes at specific indices in a space-efficient manner.

3. Dynamic Updates: The structure allows for dynamic updates to its elements through the set method, and these updates can be recorded with respect to different snapshots.

Code:

typedef struct SnapNode {
    int snap_id;
    int value;
    struct SnapNode* next;
} SnapNode;

typedef struct {
    SnapNode** snaps; // Array of linked-list heads for each index
    int length;       // Length of the SnapshotArray to ensure safe memory access
    int snapCount;    // Counter for the number of snapshots taken
} SnapshotArray;

SnapshotArray* snapshotArrayCreate(int length) {
    SnapshotArray* obj = (SnapshotArray*)malloc(sizeof(SnapshotArray));
    obj->snaps = (SnapNode**)calloc(length, sizeof(SnapNode*)); // Initialize all to NULL
    obj->length = length;
    obj->snapCount = 0;
    return obj;
}

void snapshotArraySet(SnapshotArray* obj, int index, int val) {
    if (index >= obj->length) {
        // Error handling for invalid index
        return;
    }
    // Ensure the index is valid and does not exceed the initial length
    SnapNode* newNode = (SnapNode*)malloc(sizeof(SnapNode));
    newNode->value = val;
    newNode->snap_id = obj->snapCount;
    newNode->next = obj->snaps[index];
    obj->snaps[index] = newNode;
}

int snapshotArraySnap(SnapshotArray* obj) {
    return obj->snapCount++; // Post-increment returns current value before increment
}

int snapshotArrayGet(SnapshotArray* obj, int index, int snap_id) {
    if (index >= obj->length) {
        // Error handling for invalid index
        return -1; // Returning -1 to indicate error, adjust as needed
    }
    SnapNode* node = obj->snaps[index];
    // Traverse the linked list to find the largest snap_id <= requested snap_id
    while (node && node->snap_id > snap_id) {
        node = node->next;
    }
    return node ? node->value : 0; // Return 0 if not found (default value)
}

void snapshotArrayFree(SnapshotArray* obj) {
    if (!obj) return;
    for (int i = 0; i < obj->length; i++) {
        SnapNode* node = obj->snaps[i];
        while (node) {
            SnapNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(obj->snaps);
    free(obj);
}