This problem requires designing a Number Container System that supports fast insertion, update, and retrieval of indices for each number. Using a hash table to map numbers to their indices and a separate map for index-to-number tracking ensures all operations remain efficient. GhostInterview guides you to maintain these structures while handling edge cases like duplicate updates and smallest index retrieval.
Problem Statement
Design a system that manages numbers in indexed containers with two operations: change the number at a specific index and find the smallest index for a given number. Each index can be updated multiple times, and you must always track the current number at every index.
Implement the NumberContainers class supporting the following methods: change(index, number) updates the number at the given index, and find(number) returns the smallest index currently holding that number, or -1 if none exist. Ensure that your implementation handles up to 10^5 operations efficiently with indices and numbers up to 10^9.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
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 Approach
Use Hash Maps for Fast Lookup
Maintain a hash map mapping each number to a sorted structure of indices where it appears. Also maintain a map from indices to current numbers to quickly update the system when a change occurs. This setup directly addresses the Hash Table plus Design pattern.
Handle Updates Efficiently
When changing a number at an index, first remove the index from the old number's set if present, then insert it into the new number's set. Using a priority queue or ordered set for each number ensures find operations always retrieve the smallest index efficiently.
Optimize for Time Complexity
All operations rely on log(n) time complexity due to maintaining ordered sets for each number. The system avoids scanning all indices by using hash maps for number-to-indices mapping, keeping both change and find operations fast under heavy workloads.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(\log n) |
| Space | O(n) |
Time complexity for change and find is O(log n) because updating or retrieving from a sorted set of indices per number takes logarithmic time. Space complexity is O(n) since we store mappings for each index and for all indices per number.
What Interviewers Usually Probe
- Check if candidate uses both number-to-indices and index-to-number maps correctly.
- Observe whether updates remove indices from previous numbers before insertion.
- Watch for correct handling of find when no index exists for a number.
Common Pitfalls or Variants
Common pitfalls
- Failing to remove an index from the old number's set before updating can produce incorrect find results.
- Not using a sorted structure for indices may return the wrong smallest index.
- Assuming indices are contiguous leads to inefficient O(n) searches instead of using hash maps.
Follow-up variants
- Return all indices for a number instead of just the smallest.
- Support batch updates to multiple indices at once.
- Restrict number ranges to 1-1000 to simplify storage but maintain design logic.
How GhostInterview Helps
- GhostInterview provides step-by-step guidance on building number-to-indices and index-to-number maps efficiently.
- It highlights where edge cases like duplicate updates can break naive implementations.
- It suggests optimal data structures to maintain ordered indices for fast retrieval, directly matching the problem's pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What data structures are recommended for Design a Number Container System?
Use hash maps to track number-to-indices and index-to-number relationships, and ordered sets or priority queues to maintain sorted indices for each number.
How do I handle duplicate updates at the same index?
Always remove the index from the previous number's set before inserting it into the new number's set to ensure find returns the correct smallest index.
What is the time complexity of find and change operations?
Both operations run in O(log n) time because insertion and removal in a sorted set of indices take logarithmic time.
Can numbers be negative or very large?
Yes, numbers can go up to 10^9 and indices as well, so using efficient hash maps and ordered sets is necessary for performance.
How does this problem exemplify the Hash Table plus Design pattern?
It combines hash table mapping for quick lookups with careful design of ordered index tracking to satisfy both update and retrieval constraints efficiently.
Need direct help with Design a Number Container System instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Design a Number Container System from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Design a food rating system that tracks and updates ratings of foods, finding the highest rated items by cuisine.
Open problem page#2336 Smallest Number in Infinite SetDesign a data structure to handle the smallest missing element in an infinite set, with the ability to add and remove elements efficiently.
Open problem page#2424 Longest Uploaded PrefixCalculate the longest continuous uploaded prefix in a video stream efficiently using a mix of binary search and data structures.
Open problem page