Snapshot Array

XXX. Snapshot Array

Data Structure

Binary Search

Hash Map

Problem Statement:

Design a data structure that supports taking snapshots of an array and querying the array state at a specific snapshot ID. The operations include:

• set(index, val): Update the value at the given index.
• snap(): Take a snapshot of the array and return the snapshot ID.
• get(index, snap_id): Retrieve the value at the given index from the snapshot with the specified ID.

Algorithm:

HashMap-Based Approach:

Each index in the array contains a HashMap where keys are snapshot IDs and values are the corresponding array values at that snapshot.

1. Use a HashMap at each index to store changes for different snapshots.
2. When calling snap(), increment the snapshot ID.
3. For get(), check the current snapshot or backtrack to find the most recent snapshot with a valid value.

List and Binary Search Approach:

Each index in the array contains a sorted list of Pair(snapId, value).

1. Use a list to store pairs of snapshot IDs and values at each index.
2. When calling snap(), add a new snapshot entry if the value has changed.
3. For get(), use binary search to find the most recent snapshot ID less than or equal to the queried snapshot.

Pros and Cons:

HashMap-Based Approach:

• Pros: Easy to implement and flexible for sparse updates.
• Cons: Slow get() operation due to linear search for the most recent snapshot.

List and Binary Search Approach:

• Pros: Efficient get() operation using binary search.
• Cons: More complex implementation and higher space usage for redundant entries.

Complexity:

Operation	HashMap-Based	List and Binary Search
set()	O(1)	O(1)
snap()	O(1)	O(1)
get()	O(snap_id)	O(log n)
Space	O(n * snap_id)	O(n + m)

Java Implementations:

HashMap-Based Approach:

class SnapshotArrayMap {
    Map[] arr;
    int snapIndex = 0;

    @SuppressWarnings("unchecked")
    public SnapshotArrayMap(int length) {
        arr = (Map[]) new HashMap[length];
    }

    public void set(int index, int val) {
        if (arr[index] == null) arr[index] = new HashMap<>(); // Initialize HashMap for the index
        arr[index].put(snapIndex, val); // Store value for the current snapIndex
    }

    public int snap() {
        return snapIndex++; // Increment and return the snapshot ID
    }

    public int get(int index, int snap_id) {
        Map snapMap = arr[index];
        if (snapMap == null) return 0; // If no values set, return default 0
        while (snap_id >= 0) { // Search back for the most recent snap_id
            if (snapMap.containsKey(snap_id)) return snapMap.get(snap_id);
            snap_id--; // Decrement snap_id to check previous snapshots
        }
        return 0; // Default value if no valid snap_id found
    }
}

List and Binary Search Approach:

class SnapshotArray {
    List[] arr;
    int snapIndex = 0;

    static class Pair {
        int snapId, value;

        Pair(int snapId, int value) {
            this.snapId = snapId;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    public SnapshotArray(int length) {
        arr = (List[]) new ArrayList[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>();
            arr[i].add(new Pair(-1, 0)); // Initialize with default value
        }
    }

    public void set(int index, int val) {
        List list = arr[index];
        if (list.get(list.size() - 1).snapId == snapIndex)
            list.get(list.size() - 1).value = val; // Overwrite value for current snapIndex
        else
            list.add(new Pair(snapIndex, val)); // Add new snapshot
    }

    public int snap() {
        return snapIndex++; // Increment and return the snapshot ID
    }

    public int get(int index, int snap_id) {
        List list = arr[index];
        int left = 0, right = list.size() - 1;

        // Binary search to find the most recent snap_id <= query snap_id
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).snapId <= snap_id) 
                left = mid + 1;
            else 
                right = mid - 1;
        }

        return list.get(right).value; // Most recent valid value
    }
}