953. Live Range Minimum

Medium3.5 points estimatedSegment TreeDesignArray3 hints
RPby Rohit Parihar

A warehouse keeps the unit price of items on a single shelf row, numbered from 0. Design the class LiveRangeMin, constructed from the starting prices nums.

update(index, val) replaces the price at position index with val and returns nothing. minRange(left, right) returns the lowest price among positions left through right, both included. Prices may be negative (refund slots). The operations are applied one after another in the order given, and the expected output holds the value returned by each call, using null for the constructor and for every update.

Example 1

Input:
operations = ["LiveRangeMin","minRange","update","minRange","minRange"]arguments = [[[8,3,9,5,6]],[0,4],[1,10],[0,2],[2,4]]
Output:
[null,3,null,8,5]
Explanation:

The smallest of [8,3,9,5,6] is 3. After update(1, 10) the list is [8,10,9,5,6]: positions 0..2 have minimum 8 and positions 2..4 have minimum 5.

Example 2

Input:
operations = ["LiveRangeMin","minRange","update","minRange"]arguments = [[[-1,4]],[0,1],[0,7],[0,1]]
Output:
[null,-1,null,4]
Explanation:

The minimum of [-1,4] is -1; after the first element becomes 7 the list is [7,4] and the minimum is 4.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -109 ≤ nums[i], val ≤ 109
  • 0 ≤ index < nums.length and 0 ≤ left ≤ right < nums.length
  • At most 105 calls in total

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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms

Expected complexity

Time
O(n) build, O(log n) per operation
Space
O(n)

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.