Snapshot Array Solution in Python

Problem Description

Ah, the Snapshot Array problem on LeetCode! Imagine you’re trying to keep track of your ever-changing mood throughout the day. One moment you’re happy, the next you’re grumpy because someone stole your fries. Wouldn’t it be great if you could take a snapshot of your mood at different times? Well, that’s exactly what this problem is about, but instead of moods, we’re dealing with an array that can take snapshots of its state!

In this problem, you are tasked with creating a data structure that supports the following operations:

  1. Set: Update the value at a specific index.
  2. Snap: Take a snapshot of the current state of the array.
  3. Get: Retrieve the value at a specific index from a specific snapshot.

Code Solution


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

    def set(self, index: int, val: int) -> None:
        snap = self.snaps[index][-1]
        if snap[0] == self.snap_id:
            snap[1] = val
        else:
            self.snaps[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:
        i = bisect_left(self.snaps[index], [snap_id + 1]) - 1
        return self.snaps[index][i][1]

Approach

The approach taken in this solution is quite clever. The SnapshotArray class maintains a list of snapshots for each index in the array. Each snapshot is represented as a pair of [snap_id, value]. When you set a value, it checks if the current snapshot ID matches the last one. If it does, it updates the value; if not, it creates a new snapshot. The snap method simply increments the snapshot ID, and the get method uses binary search to efficiently retrieve the value from the correct snapshot.

Time and Space Complexity

Operation Time Complexity Space Complexity
set O(1) O(N * M)
snap O(1)
get O(log N)

Real-World Example

Think of a photo album where you take pictures of your room every time you clean it. Each picture represents a snapshot of how your room looked at that moment. If someone asks you how your room looked last week, you can just flip through your album and find the right picture. Similarly, the Snapshot Array allows you to take “pictures” of the array’s state and retrieve them later.

Similar Problems

If you enjoyed this problem, you might also like these:

  • 2-Sum Solution in Python
  • 3-Sum Solution in Python
  • 4-Sum Solution in Python