Massive Algorithms: LeetCode 1146

LeetCode 1146 - Snapshot Array

https://leetcode.com/problems/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 <= 50000
At most 50000 calls will be made to set, snap, and get.
0 <= index < length
0 <= snap_id < (the total number of times we call snap())
0 <= val <= 10^9

X. Binary search
https://leetcode.com/problems/snapshot-array/discuss/350562/JavaPython-Binary-Search

    TreeMap<Integer, Integer>[] A;
    int snap_id = 0;
    public SnapshotArray(int length) {
        A = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            A[i] = new TreeMap<Integer, Integer>();
            A[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        A[index].put(snap_id, val);
    }

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

    public int get(int index, int snap_id) {
        return A[index].floorEntry(snap_id).getValue();
    }

https://leetcode.com/problems/snapshot-array/discuss/350648/Java-O(1)-snap-O(logN)-getset-using-TreeMap

    List<TreeMap<Integer, Integer>> arr;
    int currId = 0;

    public SnapshotArray(int length) {
        arr = new ArrayList();
        
        for (int i = 0; i < length; i++) {
            arr.add(i, new TreeMap<Integer, Integer>());
            arr.get(i).put(0, 0);
        }
    }
    
    public void set(int index, int val) {
        arr.get(index).put(currId, val);
    }
    
    public int snap() {
        return currId++;
    }
    
    public int get(int index, int snap_id) {
        return arr.get(index).floorEntry(snap_id).getValue();
    }

https://leetcode.com/problems/snapshot-array/discuss/350574/Java-Two-codes-w-analysis-store-difference-by-HashMap-and-TreeMap-respectively.

Store to a HashMap the set() results since previous snapshot.

Analysis:
Time: Each call of get() cost O(snap_id), othersO(1);
Space: Total cost O(n), where n is number of calls of set().

    private List<Map<Integer, Integer>> shot;
    private Map<Integer, Integer> diff;
    
    public SnapshotArray(int length) {
        shot  = new ArrayList<>(length);
        diff  = new HashMap<>(length);
    }
    
    public void set(int index, int val) {
        diff.put(index, val);
    }
    
    public int snap() {
        shot.add(diff);
        diff = new HashMap<>();
        return shot.size() - 1;
    }
    
    public int get(int index, int snap_id) {
        for (int i = snap_id; i >= 0; --i)
             if (shot.get(i).containsKey(index))   
                 return shot.get(i).get(index); 
        return 0;
    }

Method 2: TreeMap
Store the set() result together with current snapshot count to the TreeMap of the specified index.

Analysis:
Time: Instantiation cost O(length), each call of get()/set() cost O(log(count)), snap() O(1);
Space: Total cost O(length + count).

    private int count;
    private List<TreeMap<Integer, Integer>> shot = new ArrayList<>();
    
    public SnapshotArray(int length) {
        IntStream.range(0, length).forEach(i -> { shot.add(new TreeMap<>()); });
    }
    
    public void set(int index, int val) {
        shot.get(index).put(count, val);
    }
    
    public int snap() {
        return count++;
    }
    
    public int get(int index, int snap_id) {
        Integer key = shot.get(index).floorKey(snap_id);
        return key == null ? 0 : shot.get(index).get(key);
    }

https://www.cnblogs.com/lz87/p/11314526.html

Each index has its own treemap to store all needed values of different snap ids information. For a key value pair(k, v) in an index's treemap, it means starting from snap id k, until there is a newer snap, the value is v. ThisInstead of copy the whole array,

we can only record the changes of set.

Explanation

The idea is, the whole array can be large,
and we may take the snap tons of times.
(Like you may always ctrl + S twice)

Instead of record the history of the whole array,
we will record the history of each cell.
And this is the minimum space that we need to record all information.

For each A[i], we will record its history.
With a snap_id and a its value.

When we want to get the value in history, just binary search the time point.

Complexity

Time O(logS)
Space O(S)
where S is the number of set called.

SnapshotArray(int length) is O(N) time
set(int index, int val) is O(1) in Python and O(logSnap) in Java
snap() is O(1)

get(int index, int snap_id) is O(logSnap) representation helps achieve the following properties.

1. O(N) init, O(logS) get and set, where N is the total number of indices and S is the total number of snaps for an index.

2. If there is no value update at index i for consecutive snap shots, there will be only a snap_id to value mapping. When setting a new value at index i, it first check the last entry of its map, this is the latest value prior to this update operation. Only insert a new mapping if the new value is the same with the previous value, which means starting from this new snap id, the value is the new value.

3. When calling the get method, it tries to find the a key-value mapping associated with the greatest key less than or equal to the given key snap id.

class SnapshotArray {
    private TreeMap<Integer, Integer>[] snapMap;
    private int snapId = 0;
    public SnapshotArray(int length) {
        snapMap = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            snapMap[i] = new TreeMap<Integer, Integer>();
            snapMap[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        Map.Entry<Integer, Integer> lastEntry = snapMap[index].lastEntry();
        if(val != lastEntry.getValue()) {
            snapMap[index].put(snapId, val);
        }        
    }

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

    public int get(int index, int snap_id) {
        return snapMap[index].floorEntry(snap_id).getValue();
    }

https://www.acwing.com/solution/LeetCode/content/3431/

实现支持下列接口的快照数组：

SnapshotArray(int length) 初始化一个与指定长度相等的类似于数组的数据结构。初始时，每个元素都等于 0。
void set(index, val) 会将指定索引 index 处的元素设置为 val。
int snap() 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
int get(index, snap_id) 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

(数据结构，二分)

我们在普通数组的基础上进行改造，每个位置都存储一个新动态数组，存储每个版本（如果有）下的更改。
初始时，我们建立长度为 length 的数组，每个位置是一个长度为 1 的数组，仅保存版本号 0 和元素 0 的一个数对。
修改时，我们去 index 位置的数组中的最后一个位置，如果那个位置的版本号等于当前计数器的版本号，则直接修改元素值；否则新插入一个数对，记录当前版本号和元素值。
快照时，直接更新计数器。
查询时，我们得到那个位置的数组，然后开始二分，找到小于等于待查询版本的最大版本的那个数对，返回数对的元素值即可。

时间复杂度

初始化时间复杂度为 $O (l e n g t h)$ 。
修改元素的时间复杂度为 $O (1)$ 。
快照的时间复杂度为 $O (1)$ 。
查询的时间复杂度最坏为 $O (\log S)$ ，其中 $S$ 为快照的次数。

空间复杂度

最坏需要 $O (l e n g t h + Q)$ 的空间，其中 $Q$ 为操作的总次数

    vector<vector<pair<int, int>>> arr;
    int counter;

    SnapshotArray(int length) {
        arr.resize(length, vector<pair<int, int>>(1));
        for (int i = 0; i < length; i++)
            arr[i][0] = make_pair(0, 0);
        counter = 0;
    }

    void set(int index, int val) {
        auto &x = arr[index][arr[index].size() - 1];
        if (x.first == counter)
            x.second = val;
        else {
            arr[index].emplace_back(make_pair(counter, val));
        }
    }

    int snap() {
        return counter++;
    }

    int get(int index, int snap_id) {
        auto &v = arr[index];
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (snap_id >= v[mid + 1].first)
                l = mid + 1;
            else
                r = mid;
        }
        return v[l].second;
    }

X.
https://www.codetd.com/en/article/6973297

Each location to open up a space that is only saved in this location 变化
because of the number of changes in each location is not the same
when you want value, they look for less input snap_id latest变化

Use List + Map data structures to build an array of snapshots

List changes in store for each position
value after the change: TreeMap single storage changes in key: snapshot number value
Use List + Map

Examples of its structure

ArrayList + TreeMap

class SnapshotArray {
    // List 存储每个位置的变动情况
    // TreeMap 存储单次变动情况 key:快照编号 value:变动后的值
    // [index,[(snapId, val), (snapId, val)...]]
    List<TreeMap<Integer, Integer>> list = new ArrayList<>();
    // 当前快照编号
    int snapId = 0;

    // 初始化
    public SnapshotArray(int length) {
        snapId = 0;
        // 开始每个位置全为0
        for (int i = 0; i < length; i++) {
            TreeMap<Integer, Integer> t = new TreeMap<>();
            t.put(snapId, 0);
            list.add(t);
        }
    }
    
    public void set(int index, int val) {
        // 重复就覆盖
        list.get(index).put(snapId, val);
    }
    
    public int snap() {
        int res = snapId;
        snapId++;
        return res;
    }
    
    /**
     * 难点 
     * 需要在TreeMap的key值中寻找小于快照编号snap_id的数据
     * 
     * 这里取巧使用了自带的方法 
     * floorEntry(key) 找到key值接近snap_id的实体Entry
     **/
    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> t = list.get(index);
        return t.floorEntry(snap_id).getValue();
    }

X. https://leetcode.com/problems/snapshot-array/discuss/383030/Java-Binary-Search-Solution

  // int[0]: snapId, int[1]:val
  private List<int[]>[] snapshots;
  private int snapId;

  public SnapshotArray(int length) {
    snapId = 0;
    snapshots = new List[length];
    
    for (int i = 0; i < length; i++) {
      List<int[]> snapListEachItem = new ArrayList<>();
      snapListEachItem.add(new int[] {0, 0});
      snapshots[i] = snapListEachItem;
    }
    
  }

  public void set(int index, int val) {
    List<int[]> snapsOfIndex = snapshots[index];
    int[] lastSnap = snapsOfIndex.get(snapsOfIndex.size() - 1);
    
    // If last snap id is less than current id then add a new snap.
    if (lastSnap[0] < snapId) {
      snapsOfIndex.add(new int[] {snapId, val});
      return;
    }
    
    lastSnap[0] = snapId;
    lastSnap[1] = val;
  }

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

  public int get(int index, int snap_id) {
    List<int[]> snaps = snapshots[index];
    return binarySearch(snaps, snap_id);
  }
  
  private int binarySearch(List<int[]> snaps, int snapId) {
    int low = 0, high = snaps.size() - 1;
    
    while (low <= high) {
      int mid = low + (high - low) / 2;
      
      if (snaps.get(mid)[0] < snapId) {
        low = mid + 1;
      } else if (snaps.get(mid)[0] > snapId) {
        high = mid - 1;
      } else {
        return snaps.get(mid)[1];
      }
    }
    
    return low == 0 ? snaps.get(0)[1] : snaps.get(low - 1)[1];
  }