Snapshot Array and Timestamps: Version Control Design

Snapshot Array (LeetCode 1146)

Implement an array that supports snapshots. You can set values and take snaps. get(index, snap_id) should return the value of the array at the given index at the time the snapshot was taken.

Strategy: Sparse Storage + Binary Search

Instead of copying the array for every snapshot (which would be $O(length \times snaps)$), we only record changes. Each index stores a history of (snap_id, value).

class SnapshotArray {
    // Each index has a history list: [(snap_id_0, val), (snap_id_1, val), ...]
    private List<int[]>[] history;
    private int currentSnapId = 0;

    @SuppressWarnings("unchecked")
    public SnapshotArray(int length) {
        history = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            history[i] = new ArrayList<>();
            history[i].add(new int[]{0, 0}); // Initial state: snap 0 has value 0
        }
    }

    public void set(int index, int val) {
        List<int[]> entry = history[index];
        // If we've already modified this index in the current snap, update the value
        if (entry.get(entry.size() - 1)[0] == currentSnapId) {
            entry.get(entry.size() - 1)[1] = val;
        } else {
            entry.add(new int[]{currentSnapId, val});
        }
    }

    public int snap() {
        return currentSnapId++;
    }

    public int get(int index, int snap_id) {
        List<int[]> entry = history[index];
        // Binary search for the largest snap_id <= target snap_id
        int lo = 0, hi = entry.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (entry.get(mid)[0] <= snap_id) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return entry.get(lo)[1];
    }
}

Time-Based Key-Value Store (LeetCode 981)

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

class TimeMap {
    private Map<String, TreeMap<Integer, String>> store = new HashMap<>();

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) return "";
        // TreeMap.floorEntry finds the largest key <= timestamp
        Map.Entry<Integer, String> entry = store.get(key).floorEntry(timestamp);
        return entry == null ? "" : entry.getValue();
    }
}

Versioning Logic: First Bad Version (LeetCode 278)

A core logic in "Git-like" systems where we find the point of regression.

public int firstBadVersion(int n) {
    int lo = 1, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isBadVersion(mid)) {
            hi = mid; // Possible start of the "bad" streak
        } else {
            lo = mid + 1; // Everything before mid is good
        }
    }
    return lo;
}

Technical Summary

Implementation Tips

• Sparse records prevent memory bloat in versioned systems.
• Binary Search is the standard tool for querying sorted history.
• In Java, TreeMap.floorEntry(k) is an elegant built-in for finding the "last valid state before or at time $k$." 筋