Snapshot Array

Leetcode Daily Challenge (11th June, 2023)

11 June, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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

Link: https://leetcode.com/problems/snapshot-array/description/

Problem Explanation with examples:-

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.

Intuition:-

We will use a 2D array of tuples to store the history of each index based on the snap_id.
Each index of array will have a list of tuples. Each tuple will have the snap_id and the value of the index at that snap_id.
When get is called, we will use binary search to find the index of the tuple with snap_id <= given snap_id.

Solution:-

Initialize array as a 2D array of tuples with length passed and all tuples initialized with (0, 0). Initialize snap_id as 0.
Define set function which takes index and val as parameters. Append (snap_id, val) to the list at index in array.
Define snap function which increments snap_id by 1 and returns snap_id - 1.
Define get function which takes index and snap_id as parameters. Initialize history as the list at index in array. Initialize left as 0 and right as length of history - 1. Iterate until left <= right. Initialize mid as (left + right) // 2. If history[mid][0] <= snap_id, update left as mid + 1. Else, update right as mid - 1.
Return history[right][1].

Code:-

JAVA Solution

class SnapshotArray {
    private List<List<int[]>> array;
    private int snapId;

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

    public void set(int index, int val) {
        array.get(index).add(new int[]{snapId, val});
    }

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

    public int get(int index, int snapId) {
        List<int[]> history = array.get(index);
        int left = 0;
        int right = history.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (history.get(mid)[0] <= snapId) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return history.get(right)[1];
    }
}

Python Solution

class SnapshotArray:
    def __init__(self, length: int):
        self.array = [[(0, 0)] for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.array[index].append((self.snap_id, val))

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

    def get(self, index: int, snap_id: int) -> int:
        history = self.array[index]
        left, right = 0, len(history) - 1
        while left <= right:
            mid = (left + right) // 2
            if history[mid][0] <= snap_id:
                left = mid + 1
            else:
                right = mid - 1

        return history[right][1]

Complexity Analysis:-

TIME:-

The set operation has a time complexity of O(1) as it appends a new entry to the history list of the corresponding index.
The snap operation has a time complexity of O(1) as it increments the snapId.
The get operation performs a binary search on the history list, which has a time complexity of O(log H), where H is the length of the history list for the given index.

SPACE:-

The space complexity is O(N * H), where N is the length of the array and H is the maximum number of snapshots taken. The array stores the history lists for each index, and each history list can contain up to H entries.
Additionally, the snapId variable uses constant space.

References:-

Binary Search

Connect with me:-

java

python

leetcode

dsa