1119. Live Rank Counter
A weather station receives integer sensor readings as a live stream. Between readings, operators keep asking how many readings so far were at most some value. Design LiveRank to answer these questions while new readings keep arriving.
add(x)records one new readingx. The same value can be recorded many times, and every record counts separately.rank(x)returns how many recorded readings are less than or equal tox. It returns0when nothing qualifies, including before the firstadd.
Additions and queries are interleaved in any order, and the value being queried does not have to have been recorded. Re-sorting or rescanning all readings on every query will be too slow.
Example 1
- Input:
- operations = ["LiveRank","add","add","add","rank","rank","rank"]arguments = [[],[5],[3],[5],[4],[5],[2]]
- Output:
- [null,null,null,null,1,3,0]
- Explanation:
Readings are 5, 3, 5, so one reading is at most 4, all three are at most 5 (the repeated 5 counts twice), and none is at most 2.
Example 2
- Input:
- operations = ["LiveRank","rank","add","rank","add","rank","rank"]arguments = [[],[10],[0],[0],[100000],[99999],[100000]]
- Output:
- [null,0,null,1,null,1,2]
- Explanation:
The empty stream answers 0; the extreme values 0 and 100000 are both legal readings.
Constraints
1 ≤ number of operations ≤ 2 * 105
0 ≤ x ≤ 105 for both add and rank
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log V) per operation, V = 10^5 + 1
- Space
- O(V)