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:
-
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. -
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:
-
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. -
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:
-
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
ofSortedSet
is initialized to store sets of indices for each number. Thedefaultdict
from the Pythoncollections
module ensures that each number key in the dictionary will automatically be associated with an emptySortedSet
if it does not already exist in the dictionary.
- A hash map
-
Change operation (
change
method):- Given an
index
and anumber
:- If the
index
already exists in the hash map (indicating a number is already present at that index), remove the index from theSortedSet
of the current number associated with that index. - Update the hash map with the new
number
at theindex
. - Add the
index
to theSortedSet
of the new number. This operation automatically keeps theSortedSet
in sorted order.
- If the
Python code snippet for the change operation:
def change(self, index: int, number: int) -> None: if index in self.mp: v = self.mp[index] self.t[v].remove(index) self.mp[index] = number self.t[number].add(index)
- Given an
-
Find operation (
find
method):- To find the smallest index for a given
number
:- Retrieve the
SortedSet
associated with thenumber
fromself.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 thenumber
is not present at any index.
- Retrieve the
Python code snippet for the find operation:
def find(self, number: int) -> int: s = self.t[number] return s[0] if s else -1
- To find the smallest index for a given
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we initialize our NumberContainers
class and the following operations are performed sequentially:
-
change(2, 1)
: We want to insert number1
at index2
.- Since index
2
is not yet mapped, we simply insert it intoself.mp
:self.mp
becomes{2: 1}
. - We add the index to the
SortedSet
of number1
inself.t
:self.t[1]
now contains{2}
.
- Since index
-
change(1, 1)
: Now, we insert number1
at index1
.- We add the new key-value pair to
self.mp
:self.mp
becomes{2: 1, 1: 1}
. - Index
1
is added into theSortedSet
of number1
inself.t
:self.t[1]
now contains{1, 2}
, automatically sorted.
- We add the new key-value pair to
-
change(2, 2)
: Number2
is now inserted at index2
, which already has a number1
.- We remove index
2
from theSortedSet
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 theSortedSet
of number2
(which was an emptySortedSet
before):self.t[2]
now contains{2}
.
- We remove index
-
find(1)
: We want to find the smallest index where number1
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 return1
.
- Lookup
-
find(3)
: We want to find the smallest index where number3
is located.- Since number
3
has never been inserted,self.t[3]
is an emptySortedSet
. - We return
-1
, indicating that number3
is not present at any index.
- Since number
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
1# Import the defaultdict from collections and SortedSet from sortedcontainers
2from collections import defaultdict
3from sortedcontainers import SortedSet
4
5class NumberContainers:
6 def __init__(self):
7 # Dictionary to hold the current number at each index
8 self.index_to_number = {}
9 # Defaultdict to hold SortedSets which will contain indices for each number
10 # SortedSets are used for maintaining the indices in sorted order
11 self.number_to_indices = defaultdict(SortedSet)
12
13 def change(self, index: int, number: int) -> None:
14 """Update the number at the given index and maintain the indices sorted."""
15 # If the index is already in our mapping, remove it from the current number's SortedSet
16 if index in self.index_to_number:
17 current_number = self.index_to_number[index]
18 self.number_to_indices[current_number].remove(index)
19
20 # Update the number at the index in our index_to_number mapping
21 self.index_to_number[index] = number
22 # Add the index to the new number's SortedSet
23 self.number_to_indices[number].add(index)
24
25 def find(self, number: int) -> int:
26 """Returns the smallest index for the given number; if not found, returns -1."""
27 # Get the SortedSet of indices for the given number
28 indices = self.number_to_indices[number]
29 # If there are any indices, return the smallest one (first element)
30 # If not, return -1 indicating the number is not assigned to any index
31 return indices[0] if indices else -1
32
33# The NumberContainers class can now be instantiated and methods called as described.
34# obj = NumberContainers()
35# obj.change(index, number)
36# param_2 = obj.find(number)
37
1import java.util.HashMap;
2import java.util.Map;
3import java.util.TreeSet;
4
5class NumberContainers {
6 private final Map<Integer, Integer> indexToNumberMap = new HashMap<>();
7 private final Map<Integer, TreeSet<Integer>> numberToIndicesMap = new HashMap<>();
8
9 // Constructor
10 public NumberContainers() {
11 // Intentionally left blank, no initialization needed here
12 }
13
14 /**
15 * Updates the number at a given index and maintains the mapping of numbers to a sorted set of indices.
16 *
17 * @param index The index to change.
18 * @param number The new number to associate with the index.
19 */
20 public void change(int index, int number) {
21 // If index already contains a number, update the mapping
22 if (indexToNumberMap.containsKey(index)) {
23 int currentNumber = indexToNumberMap.get(index);
24 // Remove the index from the current number's set
25 TreeSet<Integer> indicesSet = numberToIndicesMap.get(currentNumber);
26 indicesSet.remove(index);
27 // If the set is empty after removal, remove it from the map
28 if (indicesSet.isEmpty()) {
29 numberToIndicesMap.remove(currentNumber);
30 }
31 }
32 // Add or update the index-to-number mapping
33 indexToNumberMap.put(index, number);
34 // Add index to the new number's set, creating the set if it doesn't exist
35 numberToIndicesMap.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
36 }
37
38 /**
39 * Finds the lowest index for a number.
40 * If the number is not associated with any index, returns -1.
41 *
42 * @param number The number to find the lowest index for.
43 * @return The lowest index of the given number or -1 if not found.
44 */
45 public int find(int number) {
46 // Check if number exists in the map and return the first (lowest) index
47 return numberToIndicesMap.containsKey(number) ? numberToIndicesMap.get(number).first() : -1;
48 }
49}
50
51// The NumberContainers object usage remains the same; example of instantiation and method calls:
52// NumberContainers obj = new NumberContainers();
53// obj.change(index,number);
54// int lowestIndex = obj.find(number);
55
1#include <map>
2#include <set>
3
4class NumberContainers {
5public:
6 // Maps each index to the number it contains.
7 std::map<int, int> indexToNumberMap;
8
9 // Maps each number to a set of indices that contain this number.
10 std::map<int, std::set<int>> numberToIndicesMap;
11
12 // Default constructor.
13 NumberContainers() {
14 }
15
16 // Changes the number at the given index.
17 void change(int index, int number) {
18 // Check if the index is already in the map.
19 auto it = indexToNumberMap.find(index);
20 if (it != indexToNumberMap.end()) {
21 // If the index is already there, remove the index from the set corresponding
22 // to its current number, as it's about to be reassigned.
23 numberToIndicesMap[it->second].erase(index);
24 // Update the index to the new number.
25 it->second = number;
26 } else {
27 // If the index is new, just add it to the map.
28 indexToNumberMap[index] = number;
29 }
30 // Insert the index to the set corresponding to the new number.
31 numberToIndicesMap[number].insert(index);
32 }
33
34 // Finds the smallest index that contains the given number. Returns -1 if such an index cannot be found.
35 int find(int number) {
36 // Attempt to find the set of indices for the given number.
37 auto it = numberToIndicesMap.find(number);
38 // If the number is not found or the set is empty, return -1.
39 return (it == numberToIndicesMap.end() || it->second.empty()) ? -1 : *it->second.begin();
40 }
41};
42
43/**
44 * The NumberContainers object will be instantiated and called like this:
45 * NumberContainers* obj = new NumberContainers();
46 * obj->change(index, number);
47 * int param_2 = obj->find(number);
48 */
49
1// Mapping from index to number.
2const indexToNumberMap: Map<number, number> = new Map();
3
4// Mapping from number to a set of indices containing that number.
5const numberToIndicesMap: Map<number, Set<number>> = new Map();
6
7/**
8 * Changes the number at the given index.
9 * @param index The index of the number to change.
10 * @param number The new number to set at the index.
11 */
12function change(index: number, number: number): void {
13 // Check if the index already maps to a number.
14 if (indexToNumberMap.has(index)) {
15 // Retrieve the current number at the index.
16 const currentNumber = indexToNumberMap.get(index);
17 // Remove index from the set of the current number.
18 numberToIndicesMap.get(currentNumber)?.delete(index);
19 }
20 // Update the index to the new number.
21 indexToNumberMap.set(index, number);
22
23 // If there's no existing set for this number, create one.
24 if (!numberToIndicesMap.has(number)) {
25 numberToIndicesMap.set(number, new Set());
26 }
27 // Add the index to the set corresponding to the new number.
28 numberToIndicesMap.get(number)?.add(index);
29}
30
31/**
32 * Finds the smallest index that contains the given number.
33 * @param number The number to find the smallest index for.
34 * @returns The smallest index containing the given number, or -1 if not found.
35 */
36function find(number: number): number {
37 // Attempt to find the set of indices for the given number.
38 const indicesSet = numberToIndicesMap.get(number);
39 // If there's no set for the number or the set is empty, return -1.
40 if (!indicesSet || indicesSet.size === 0) {
41 return -1;
42 }
43 // Return the smallest index (first value) in the sorted set.
44 return Math.min(...indicesSet);
45}
46
47// Example usage:
48// change(1, 10);
49// let smallestIndex = find(10);
50// console.log(smallestIndex); // Outputs the smallest index where the number 10 is located, if present.
51
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 ofO(1)
, as it only involves the initialization of two data structures: a dictionaryself.mp
and a defaultdict of SortedSetself.t
. -
change
function: Thechange
method has a time complexity ofO(log n)
for updating the SortedSet in the case where the index already exists inself.mp
, since SortedSet removes the element inO(log n)
and adds the element inO(log n)
time complexity. If an element is not present, adding to a SortedSet isO(log n)
as well. Updating the dictionaryself.mp
has a time complexity ofO(1)
. -
find
function: Thefind
method has a time complexity ofO(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 isO(1)
as it initializes empty data structures. -
change
andfind
functions: The space complexity isO(m + k)
wherem
is the number of unique indices andk
is the total number of unique numbers present in the NumberContainers object. This is becauseself.mp
can potentially hold a mapping for each unique index andself.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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!