2349. Design a Number Container System

Problem Description

The LeetCode problem entails designing a system that can manage a set of numbers each located at a unique index. The system needs to support two primary operations:

1. change: This operation must insert or replace a number at a specified index. If an index already contains a number, it should be replaced with the new number.

2. find: This operation should return the smallest index at which a specific number is located. If the number is not present in any container, the system should return -1.

The challenge is to implement these operations efficiently, meaning we need to optimize for both insert/replace and search operations, ensuring that find queries are performed in an optimized manner, especially in a dataset where searches are frequent compared to updates.

Intuition

To arrive at the solution, we need a data structure that can efficiently keep track of each number's indices and quickly retrieve the smallest index of any given number. We use two main data structures to achieve this:

1. A hash map (self.mp), where the key is the index and the value is the number at that index. This allows us to quickly check if an index already has a number and to update the number at any index.

2. A default dictionary of SortedSet (self.t), indexed by numbers. SortedSet is a data structure that maintains the elements in sorted order. This allows us to quickly retrieve the smallest index for a given number as it will always be the first element.

When we perform the change operation, we update the index's number in the hash map. If the index already had a number, we remove the index from the SortedSet of that old number. Then we add the index to the SortedSet of the new number.

During the find operation, we look up the SortedSet for the given number. If the SortedSet is not empty, we return the first element (since it's the smallest index due to the properties of the SortedSet). If the SortedSet is empty, it means the number is not present at any index, so we return -1.

This approach allows us to efficiently update the indices and retrieve the smallest index for any number, making the NumberContainers class a fast and reliable system for the operations required.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation of the NumberContainers class uses a hash map and a default dictionary of SortedSet structures. The SortedSet is chosen for its properties of maintaining the elements in sorted order, which is essential for efficient retrieval of indices.

Here's a step-by-step breakdown of the implementation:

1. Initialization (__init__ method):

   • A hash map self.mp is initialized to keep track of which number is at which index.
   • A default dictionary self.t of SortedSet is initialized to store sets of indices for each number. The defaultdict from the Python collections module ensures that each number key in the dictionary will automatically be associated with an empty SortedSet if it does not already exist in the dictionary.

2. Change operation (change method):

   • Given an index and a number:
     • If the index already exists in the hash map (indicating a number is already present at that index), remove the index from the SortedSet of the current number associated with that index.
     • Update the hash map with the new number at the index.
     • Add the index to the SortedSet of the new number. This operation automatically keeps the SortedSet in sorted order.

   Python code snippet for the change operation:

   1def change(self, index: int, number: int) -> None:
   2    if index in self.mp:
   3        v = self.mp[index]
   4        self.t[v].remove(index)
   5    self.mp[index] = number
   6    self.t[number].add(index)

3. Find operation (find method):

   • To find the smallest index for a given number:
     • Retrieve the SortedSet associated with the number from self.t.
     • If the SortedSet is not empty, return the first element (smallest index) since the indices are maintained in sorted order.
     • If the SortedSet is empty, return -1 indicating the number is not present at any index.

   Python code snippet for the find operation:

   1def find(self, number: int) -> int:
   2    s = self.t[number]
   3    return s[0] if s else -1

The choice of SortedSet is crucial for the solution's efficiency. SortedSet allows for fast addition and removal of index elements while maintaining a sort order, making the find operation a simple and quick retrieval of the smallest element. This solution thus capably balances the need for dynamic updates with frequent and fast queries, delivering the functionalities required by the NumberContainers system.

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we initialize our NumberContainers class and the following operations are performed sequentially:

1. change(2, 1): We want to insert number 1 at index 2.

   • Since index 2 is not yet mapped, we simply insert it into self.mp: self.mp becomes {2: 1}.
   • We add the index to the SortedSet of number 1 in self.t: self.t[1] now contains {2}.

2. change(1, 1): Now, we insert number 1 at index 1.

   • We add the new key-value pair to self.mp: self.mp becomes {2: 1, 1: 1}.
   • Index 1 is added into the SortedSet of number 1 in self.t: self.t[1] now contains {1, 2}, automatically sorted.

3. change(2, 2): Number 2 is now inserted at index 2, which already has a number 1.

   • We remove index 2 from the SortedSet of the old number, self.t[1], which then becomes {1}.
   • self.mp is updated to reflect the change: self.mp becomes {2: 2, 1: 1}.
   • Index 2 is added to the SortedSet of number 2 (which was an empty SortedSet before): self.t[2] now contains {2}.

4. find(1): We want to find the smallest index where number 1 is located.

   • Lookup self.t[1], which contains {1}.
   • The smallest index in the sorted set is the first element, which is 1, thus we return 1.

5. find(3): We want to find the smallest index where number 3 is located.

   • Since number 3 has never been inserted, self.t[3] is an empty SortedSet.
   • We return -1, indicating that number 3 is not present at any index.

The sequence of these operations would result in the following internal states for our NumberContainers class:

• Hash map of index to numbers: self.mp = {1: 1, 2: 2}
• Default dictionary of number to SortedSets of indices: self.t = {1: SortedSet([1]), 2: SortedSet([2])}

This example demonstrates how each change and find operation works as expected, providing efficient updates and lookups as per the problem requirements.

Solution Implementation

Time and Space Complexity

The given Python code defines a class NumberContainers that manages a mapping between indices and numbers and provides two methods: change to change the number at a given index, and find to find the smallest index with a given number.

Time complexity:

• __init__ function: The initialization function has a constant time complexity of O(1), as it only involves the initialization of two data structures: a dictionary self.mp and a defaultdict of SortedSet self.t.

• change function: The change method has a time complexity of O(log n) for updating the SortedSet in the case where the index already exists in self.mp, since SortedSet removes the element in O(log n) and adds the element in O(log n) time complexity. If an element is not present, adding to a SortedSet is O(log n) as well. Updating the dictionary self.mp has a time complexity of O(1).

• find function: The find method has a time complexity of O(1) for accessing the first element of the SortedSet since SortedSet maintains the elements in sorted order, and accessing the elements by index is done in constant time.

Space complexity:

• __init__ function: The space complexity for the initialization function is O(1) as it initializes empty data structures.

• change and find functions: The space complexity is O(m + k) where m is the number of unique indices and k is the total number of unique numbers present in the NumberContainers object. This is because self.mp can potentially hold a mapping for each unique index and self.t holds unique numbers each associated with a SortedSet which in turn contains indices.

Overall, this data structure is optimized for quick updates and lookups, with the SortedSet providing efficient ordering for the indices.

Learn more about how to find time and space complexity quickly using problem constraints.