Formatted question description: https://leetcode.ca/all/2349.html

2349. Design a Number Container System

Difficulty: Medium.
Related Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set.
Similar Questions: Seat Reservation Manager, Design a Food Rating System.

Problem

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 at index with the number. If there is already a number at that index, replace it.
int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number 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 to change and find.

Solution (Java, C++, Python)

class NumberContainers {
    private Map<Integer, TreeSet<Integer>> indices = new HashMap<>();
    private Map<Integer, Integer> vals = new HashMap<>();

    public NumberContainers() {}

    public void change(int index, int number) {
        if (vals.containsKey(index)) {
            int old = vals.get(index);
            indices.get(old).remove(index);
            if (indices.get(old).isEmpty()) {
                indices.remove(old);
            }
        }
        vals.put(index, number);
        indices.computeIfAbsent(number, s -> new TreeSet<>()).add(index);
    }

    public int find(int number) {
        if (indices.containsKey(number)) {
            return indices.get(number).first();
        }
        return -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 {
    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);
 */

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)

############

# 2349. Design a Number Container System
# https://leetcode.com/problems/design-a-number-container-system/

from sortedcontainers import SortedList

class NumberContainers:

    def __init__(self):
        self.A = {}
        self.sl = defaultdict(SortedList)

    def change(self, index: int, number: int) -> None:
        if index in self.A:
            prevNumber = self.A[index]
            self.sl[prevNumber].remove(index)
            
        self.A[index] = number
        self.sl[number].add(index)
        

    def find(self, number: int) -> int:
        s = self.sl[number]
        
        if not s: return -1
        
        return s[0]

# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# 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);
 */

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);
 */

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).

2349 - Design a Number Container System

2349. Design a Number Container System

Problem

Solution (Java, C++, Python)

All Problems

All Solutions

Welcome to Subscribe On Youtube

2349. Design a Number Container System

Problem

Solution (Java, C++, Python)

All Problems

All Solutions