Leetcode 1146 - Snapshot Array

Link to problem

Description

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.

Solution

Of course we could not copy everything when a snapshot is taken. Therefore, we store our data using an array of map. When get() is called, we find the value of the snap shot which has id closest to snap_id but <= snap_id.

Implementation

My first implementation uses unordered_map. In get(), the function counts down from snap_id and tries to find an existing snapshot id.

class SnapshotArray {
private:
    vector<unordered_map<int, int>> snapshots;
    int snapshotCount = 0;

public:
    SnapshotArray(int length): snapshots(length) {
        for (int i = 0; i < length; i++) {
            snapshots[i][0] = 0;
        }
    }

    void set(int index, int val) {
        snapshots[index][snapshotCount] = val;
    }

    int snap() {
        snapshotCount++;
        return snapshotCount - 1;
    }

    int get(int index, int snap_id) {
        auto& snaps = snapshots[index];
        while (snaps.find(snap_id) == snaps.end()) { snap_id--; };
        return snaps[snap_id];
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

Later I found out that there exists a iterator upper_bound(const Key& key); that returns an iterator pointing to the first element that is greater than key. With the use of this method the speed of get() could be improved by some degree. However, this method only exist in map but not unordered_map as its name suggests, unordered_map does not preserve the insert order.

class SnapshotArray {
private:
    vector<map<int, int>> snapshots;
    int snapshotCount = 0;

public:
    // other methods are the same stuff, ignored here.

    int get(int index, int snap_id) {
        auto it = snapshots[index].upper_bound(snap_id);
        it--;
        return it->second;
    }
};