Design a mutable container system that supports updating values at indices and quickly finding the smallest index holding a given value.
Build a data structure that stores integers at numbered indices and supports two operations:
The key challenge is to make find(number) fast even after many updates.
A correct design must handle reassigning an index from one number to another and keep the internal state consistent at all times.
This is an API design problem.
Implement a class with the following operations:
change(index, number): set the value at index to number.find(number): return the smallest index whose current value is number, or -1 if no such index exists.For each find(number) call, return the smallest valid index for that number, or -1 when the number is absent.
index and number are positive integers.change may target the same index.Typical interview solution targets O(log n) or better per operation.
Example 1
Input
change(1, 10) change(2, 10) find(10) change(1, 20) find(10) find(20)
Output
1 2 1
Explanation
After the first two updates, number 10 is stored at indices 1 and 2, so the smallest is 1. Reassigning index 1 to 20 removes it from the set for 10, leaving 2 as the smallest index for 10 and 1 as the index for 20.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.