Algorithm

Problem Name: 1146. Snapshot Array

Problem Link: 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 <= 5 * 104
  • 0 <= index < length
  • 0 <= val <= 109
  • 0 <= snap_id < (the total number of times we call snap())
  • At most 5 * 104 calls will be made to set, snap, and get.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


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

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

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

  public int get(int index, int snap_id) {
    return A[index].floorEntry(snap_id).getValue();
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

x
–
+
cmd
[null,null,0,null,5]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const SnapshotArray = function(length) {
  this.snaps = Array(length)
  this.snapId = 0
};

SnapshotArray.prototype.set = function(index, val) {
  if(this.snaps[index] == null) {
    this.snaps[index] = {}
  }
  this.snaps[index][this.snapId] = val
};

SnapshotArray.prototype.snap = function() {
  return this.snapId++
};

SnapshotArray.prototype.get = function(index, snap_id) {
  let res = 0
  let id = snap_id
  while(id >= 0) {
    if(this.snaps[index] == null || this.snaps[index][id] == null) id--
    else {
      res = this.snaps[index][id]
      break
    }
  }
  
  return res
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

x
–
+
cmd
[null,null,0,null,5]

#3 Code Example with Python Programming

Code - Python Programming

start coding...
class SnapshotArray:

    def __init__(self, length: int):
        self.s = 0
        self.arr = [[[0, 0]] for i in range(length)]

    def set(self, index: int, val: int) -> None:
        if self.s == self.arr[index][-1][0]:
            self.arr[index][-1][1] = val
        else:
            self.arr[index].append([self.s, val])

    def snap(self) -> int:
        self.s += 1
        return self.s - 1

    def get(self, index: int, snap_id: int) -> int:
        i = bisect.bisect_left(self.arr[index], [snap_id])
        if i < len(self.arr[index]):
            if self.arr[index][i][0] > snap_id:
                i -= 1
            return self.arr[index][i][1]
        return self.arr[index][-1][1]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]]

Output

x
–
+
cmd
[null,null,0,null,5]
Advertisements

Demonstration

Previous
#1145 Leetcode Binary Tree Coloring Game Solution in C, C++, Java, JavaScript, Python, C# LeetcodeProblem Name:
Next
#1147 Leetcode Longest Chunked Palindrome Decomposition Solution in C, C++, Java, JavaScript, Python, C# Leetcode