Skip to the code
cf.
+25 XP

#685 Range Peak With Edits

medium

A server monitor shows memory use per second and lets you pick any time range to see its peak. Readings can be corrected after the fact. Write a class PeakTracker:

  • new PeakTracker(readings) starts with the readings.
  • set(index, value) replaces reading index with value.
  • peak(left, right) returns the largest reading from left to right, inclusive.

Each call should take O(log n) time.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new PeakTracker(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["PeakTracker","peak","set","peak","peak"]
[[[4,9,2,7,5]],[0,4],[1,1],[0,4],[2,4]]
Output: [null,9,null,7,7]

The peak is 9 until it is corrected to 1; then it is 7.

Example 2

Input: ["PeakTracker","peak"]
[[[3]],[0,0]]
Output: [null,3]

One reading is its own peak.

Constraints

  • 1 <= readings.length <= 10^5
  • -10^9 <= readings[i], value <= 10^9
  • 0 <= left <= right < readings.length
  • At most 10^5 calls.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).