1478. Rain Gauge Log

Easy1.5 points estimatedBinary SearchPrefix SumDesignData Stream
RPby Rohit Parihar

A weather station records rainfall once per day. Implement RainGaugeLog: logRain(mm) records the rainfall of the next day, numbering the days 0, 1, 2, ... in the order they are logged, with mm >= 0.

firstDayReaching(total) returns the smallest logged day d such that the cumulative rainfall of days 0 through d is at least total, or -1 if the logged days have not reached it yet. If several days tie because rain stopped, the earliest day is returned.

totalBetween(fromDay, toDay) returns the inclusive sum of rainfall from fromDay to toDay, both of them already logged. Keep running totals so that logging is O(1), the reach query is a binary search O(log d) and the range sum is O(1). Use 64-bit integers for sums.

Example 1

Input:
operations = ["RainGaugeLog","logRain","logRain","logRain","firstDayReaching","firstDayReaching","totalBetween","totalBetween"]arguments = [[],[4],[0],[7],[5],[12],[1,2],[0,2]]
Output:
[null,null,null,null,2,-1,7,11]
Explanation:

The cumulative totals are 4, 4, 11, so total 5 is first reached on day 2, 12 is never reached, and the two range sums are 7 and 11.

Example 2

Input:
operations = ["RainGaugeLog","firstDayReaching","logRain","firstDayReaching","logRain","firstDayReaching","firstDayReaching","firstDayReaching","totalBetween","totalBetween"]arguments = [[],[1],[0],[1],[3],[1],[3],[4],[0,0],[1,1]]
Output:
[null,-1,null,-1,null,1,1,-1,0,3]
Explanation:

Nothing is logged at first so the query returns -1; after days of 0 and 3 rainfall, total 1 and 3 are reached on day 1, total 4 is not reached.

Constraints

at most 1000 calls in total

0 ≤ mm ≤ 104

1 ≤ total ≤ 1012

0 ≤ fromDay ≤ toDay < number of days logged

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. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case
Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms

Expected complexity

Time
O(1) log, O(log d) reach, O(1) range
Space
O(d)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.