Skip to main content
Talentd

Design a Number Container System - Solution & Explanation

MediumHash TableDesignHeap (Priority Queue)Ordered Set22 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You need to design a data structure that supports two operations: change(index, number) which assigns a number to an index, and find(number) which returns the smallest index currently storing that number. The challenge is handling frequent updates while always retrieving the minimum index efficiently.

Approach 1: HashMap + Ordered Set (O(log n) per operation)

Maintain two structures: a hash map indexToNumber that records the current number stored at each index, and another map numberToIndices where each number points to an ordered set of indices. When change(index, number) is called, check if the index already holds a value. If it does, remove that index from the ordered set of the previous number. Then insert the index into the ordered set of the new number and update indexToNumber. The find(number) operation simply returns the smallest element from the ordered set (e.g., TreeSet.first()). Insertions and removals in the ordered set cost O(log n), while lookups in the hash map are O(1). Space complexity is O(n). This approach relies heavily on hash tables and an ordered set structure.

Approach 2: Two HashMaps + Min Heap with Lazy Cleanup (O(log n) amortized)

Instead of maintaining a perfectly clean ordered set, store indices for each number in a min heap. Use indexToNumber to track the latest value assigned to each index, and numberToHeap where each number maps to a min heap of indices. Every time change(index, number) runs, push the index into the heap for that number and update indexToNumber. Old entries are not removed immediately. During find(number), repeatedly check the heap's top element. If the index at the top no longer maps to that number in indexToNumber, discard it. Continue until a valid index appears or the heap becomes empty. Each heap push or pop costs O(log n), and lazy deletion keeps updates simple. Total space complexity remains O(n). This method uses hash tables and a heap (priority queue).

Recommended for interviews: The ordered set solution is the cleanest and easiest to reason about. Interviewers like it because every structure always stays consistent and each operation has a clear O(log n) bound. The heap-based approach is also acceptable and commonly used in languages without a built-in ordered set. Showing both demonstrates strong understanding of data structure design and tradeoffs between strict ordering and lazy cleanup strategies.

Approach 1: Using HashMaps and SortedMap

In this approach, we use two main data structures:

  • A map (or dictionary) to track the number at each index. This allows us to efficiently get or update the number for a specific index.
  • A SortedMap (or TreeMap equivalent) for each unique number to maintain indices in sorted order.

The initial idea is to map each index to its number and, for each number, keep a sorted set of indices where the number occurs. This allows us to quickly access the smallest index for any number.

This Python implementation uses the sortedcontainers library to efficiently maintain a sorted set of indices for each number. The change method updates the current index with the new number and ensures indices for the old number are updated. The find method returns the smallest index from the sorted set.

Code

PythonJava

Python

Java

Complexity

Time Complexity:
change: O(log N), where N is the number of indices tracked for a number.
find: O(1) on average since accessing the minimum index is direct.
Space Complexity: O(N + M), where N is the number of indices and M is the number of unique numbers.

Try this approach in the editor →

Approach 2: Using Two HashMaps

In this approach, we can optimize by using two hash maps:

  • indexToNumber to map each index to its current number.
  • numberToIndices to map each number to a min-heap of indices (using a custom data structure).

This provides efficient data management for the system with an alternative focus on comprehensive hash map manipulation.

This C++ implementation uses an unordered map to track the number at each index and a set for sorted index tracking for each number. Both data structures allow for efficient operations on updates and retrievals.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity:
change: O(log N) due to set operations.
find: O(1) by accessing the first element of a set.
Space Complexity: O(N + M), where N and M are sizes of index and number maps.

Try this approach in the editor →

Approach 3: Hash Table + Ordered Set

We use a hash table d to record the mapping relationship between indices and numbers, and another hash table g to record the set of indices corresponding to each number. Here, we can use an ordered set to store the indices, which allows us to conveniently find the smallest index.

When calling the change method, we first check if the index already exists. If it does, we remove the original number from its corresponding index set and then add the new number to the corresponding index set. The time complexity is O(log n).

When calling the find method, we simply return the first element of the index set corresponding to the number. The time complexity is O(1).

The space complexity is O(n), where n is the number of numbers.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using HashMaps and SortedMap

Time Complexity:
change: O(log N), where N is the number of indices tracked for a number.
find: O(1) on average since accessing the minimum index is direct.
Space Complexity: O(N + M), where N is the number of indices and M is the number of unique numbers.

Using Two HashMaps

Time Complexity:
change: O(log N) due to set operations.
find: O(1) by accessing the first element of a set.
Space Complexity: O(N + M), where N and M are sizes of index and number maps.

Hash Table + Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap + Ordered SetO(log n) per operationO(n)Best when language supports TreeSet/SortedSet for direct smallest-index lookup
Two HashMaps + Min Heap (Lazy Deletion)O(log n) amortizedO(n)Useful in languages without ordered sets; heap cleanup happens during queries

Video Solution

Design a Number Container System | 2 Approaches | Leetcode 2349 | codestorywithMIK • codestorywithMIK • 7,813 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design a Number Container System easy or hard?
The problem is rated Medium because the logic requires coordinating multiple data structures and handling updates correctly. The individual operations are simple, but maintaining consistency between mappings and ensuring the smallest index is returned makes it slightly tricky.
Design a Number Container System Python or Java solution
Python implementations typically use a dictionary with heapq for each number and lazy deletion to remove outdated indices. Java solutions often use HashMap combined with TreeSet, allowing direct retrieval of the smallest index using first(). Both achieve O(log n) operations.
How to solve Design a Number Container System in O(log n)?
Maintain two mappings: indexToNumber to track the current value at each index, and numberToIndices which stores all indices for a number in a sorted structure like TreeSet or a min heap. Updates adjust the index membership, while queries return the smallest stored index. Ordered structures ensure O(log n) insertion and removal.
What is the best approach for Design a Number Container System?
The most reliable approach uses a HashMap and an ordered set (such as TreeSet). A map stores index -> number while another map stores number -> sorted set of indices. Each change operation updates both structures and find(number) simply returns the smallest index from the set. Both operations run in O(log n) time with O(n) space.
Is Design a Number Container System asked at Google/Amazon/Meta?
Design-style data structure problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question evaluates understanding of hash maps, heaps, and ordered sets along with the ability to maintain consistent state across multiple data structures.
What data structure is used in Design a Number Container System?
The core structures are hash tables for constant-time mapping and either an ordered set (TreeSet / SortedSet) or a min heap to maintain the smallest index for each number. These structures together allow efficient updates and queries.
What is the time complexity of Design a Number Container System?
Using the optimal design, both change(index, number) and find(number) run in O(log n) time because indices are inserted or removed from a balanced ordered set or heap. Hash map lookups remain O(1). Overall space complexity is O(n) to store mappings between indices and numbers.

Ready to solve this problem?

Practice Design a Number Container System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design a Food Rating System

Next

Seat Reservation Manager