We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Snapshot Array

Difficulty: Medium

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.

Key Insights

  • The structure must support getting historical values efficiently.
  • A snapshot mechanism is needed to save the state of the array at a given point in time.
  • Each index may have multiple values corresponding to different snapshots.

Space and Time Complexity

Time Complexity: O(1) for set and snap operations, O(log(n)) for get operations if a binary search is needed (depending on implementation). Space Complexity: O(n * m) where n is the length of the array and m is the number of snapshots, in the worst case.

Solution

To solve this problem, we will use a combination of a list (or array) to store the current values and a list of dictionaries (or maps) to store the snapshots. Each time we call snap(), we will save the current state of the array in the snapshot list. The get() method will look up the value in the corresponding snapshot using the snap_id. This approach allows us to efficiently capture and retrieve historical data.

Code Solutions

class SnapshotArray:
    def __init__(self, length: int):
        self.snapshots = [{}]  # List to hold snapshots as dictionaries
        self.current = [0] * length  # Initialize the current state to 0
        self.snap_id = 0  # Counter for snapshots

    def set(self, index: int, val: int) -> None:
        self.current[index] = val  # Set the value at the specified index

    def snap(self) -> int:
        self.snapshots.append(self.current.copy())  # Store a copy of the current state
        self.snap_id += 1  # Increment the snapshot ID
        return self.snap_id - 1  # Return the last snapshot ID

    def get(self, index: int, snap_id: int) -> int:
        return self.snapshots[snap_id].get(index, 0)  # Get the value from the snapshot
← Back to All Questions