LeetCode Daily Problem P2349: Design a Number Container System

---

Timeline

Timeline

2025-09-17

init

Understanding of STL containers map and set

---

Problem:

P2349 Design a Number Container System

https://leetcode.cn/problems/design-a-number-container-system/description/?envType=daily-question&envId=2025-09-17

This problem mainly uses the idea of trading space for time. Based on the ranges of index and number given in the hints, it can be concluded that a brute-force solution will definitely TLE, and indeed that is the case.
Utilize the characteristics of set: std::set is internally a balanced binary search tree (usually a red-black tree). The smallest element in the tree is always at the far left → set.begin() points to the leftmost leaf node. Therefore rbegin() returns the maximum value.

#include <map>
#include <set>
class NumberContainers {
public:
  NumberContainers() {}

  void change(int index, int number) {

    if (map.count(index)) { // The map already has this index.
      int last_number = map[index];
      min_map[last_number].erase(index);
    }
    map[index] = number;
    min_map[number].insert(index);
  }

  int find(int number) {
    if (min_map.count(number) && !min_map[number].empty()) {
      return *min_map[number].begin();
    } else {
      return -1;
    }
  }

private:
  std::map<int, int> map;
  std::map<int, std::set<int>> min_map;
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 *      NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */