Welcome to Subscribe On Youtube
2349. Design a Number Container System
Description
Design a number container system that can do the following:
- Insert or Replace a number at the given index in the system.
- Return the smallest index for the given number in the system.
Implement the NumberContainers
class:
NumberContainers()
Initializes the number container system.void change(int index, int number)
Fills the container atindex
with thenumber
. If there is already a number at thatindex
, replace it.int find(int number)
Returns the smallest index for the givennumber
, or-1
if there is no index that is filled bynumber
in the system.
Example 1:
Input ["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"] [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]] Output [null, -1, null, null, null, null, 1, null, 2] Explanation NumberContainers nc = new NumberContainers(); nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1. nc.change(2, 10); // Your container at index 2 will be filled with number 10. nc.change(1, 10); // Your container at index 1 will be filled with number 10. nc.change(3, 10); // Your container at index 3 will be filled with number 10. nc.change(5, 10); // Your container at index 5 will be filled with number 10. nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1. nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.
Constraints:
1 <= index, number <= 109
- At most
105
calls will be made in total tochange
andfind
.
Solutions
-
class NumberContainers { private Map<Integer, Integer> mp = new HashMap<>(); private Map<Integer, TreeSet<Integer>> t = new HashMap<>(); public NumberContainers() { } public void change(int index, int number) { if (mp.containsKey(index)) { int v = mp.get(index); t.get(v).remove(index); if (t.get(v).isEmpty()) { t.remove(v); } } mp.put(index, number); t.computeIfAbsent(number, k -> new TreeSet<>()).add(index); } public int find(int number) { return t.containsKey(number) ? t.get(number).first() : -1; } } /** * Your NumberContainers object will be instantiated and called as such: * NumberContainers obj = new NumberContainers(); * obj.change(index,number); * int param_2 = obj.find(number); */
-
class NumberContainers { public: map<int, int> mp; map<int, set<int>> t; NumberContainers() { } void change(int index, int number) { auto it = mp.find(index); if (it != mp.end()) { t[it->second].erase(index); it->second = number; } else mp[index] = number; t[number].insert(index); } int find(int number) { auto it = t.find(number); return it == t.end() || it->second.empty() ? -1 : *it->second.begin(); } }; /** * Your NumberContainers object will be instantiated and called as such: * NumberContainers* obj = new NumberContainers(); * obj->change(index,number); * int param_2 = obj->find(number); */
-
from sortedcontainers import SortedSet class NumberContainers: def __init__(self): self.mp = {} self.t = defaultdict(SortedSet) 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) def find(self, number: int) -> int: s = self.t[number] return s[0] if s else -1 # Your NumberContainers object will be instantiated and called as such: # obj = NumberContainers() # obj.change(index,number) # param_2 = obj.find(number)
-
type NumberContainers struct { mp map[int]int t map[int]*redblacktree.Tree } func Constructor() NumberContainers { return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree{} } } func (this *NumberContainers) Change(index int, number int) { if num, ok := this.mp[index]; ok { this.t[num].Remove(index) } this.mp[index] = number if this.t[number] == nil { this.t[number] = redblacktree.NewWithIntComparator() } this.t[number].Put(index, nil) } func (this *NumberContainers) Find(number int) int { s, ok := this.t[number] if !ok || s.Size() == 0 { return -1 } return s.Left().Key.(int) } /** * Your NumberContainers object will be instantiated and called as such: * obj := Constructor(); * obj.Change(index,number); * param_2 := obj.Find(number); */