LeetCode Daily Problem P2349 Design Number Container System

---

Timeline

Timeline

2025-09-17

init

Understanding of STL containers map and set

---

Problem:

P2349 Design 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. According to the given range of index and number, it can be concluded that the brute force solution will definitely TLE, and indeed it does.
Using the characteristics of set: std::set internally is a balanced binary search tree (usually a red-black tree). The smallest element in the tree is always on the leftmost side → 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 originally 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);
 */