Frontend School

Dynamic Range Maximum

DSA
medium

Dynamic Range Maximum

Medium
Segment Tree
Lazy Propagation
Data Structures
Range Query
Range Update

Overview

In many real-world applications, such as financial trading platforms, sensor data analysis, or game development, we often need to efficiently track and update values over dynamic ranges. For instance, imagine a system monitoring stock prices where a certain event might cause all stocks in a particular sector to increase by a fixed percentage, and you frequently need to find the highest price within a given portfolio range. This problem challenges you to design a data structure that can handle both range updates (adding a value to all elements within a specified range) and range queries (finding the maximum value within a specified range) efficiently.

What you need to do / Task

Implement a class DynamicRangeMaximum that supports the following operations:

  1. Constructor: Initializes the data structure with an initial array of numbers.
  2. updateRange(left, right, value): Adds value to each element in the array from index left to right (inclusive).
  3. queryMax(left, right): Returns the maximum value among elements in the array from index left to right (inclusive).

Your solution should provide optimal time complexity for both update and query operations.

Input & output

DynamicRangeMaximum(initialArray: number[])

  • initialArray: An array of numbers representing the initial state of the data. Its length N can be up to 10^5.
  • Returns: Nothing. Initializes the internal data structure.

updateRange(left: number, right: number, value: number): void

  • left: The starting index of the range (0-indexed).
  • right: The ending index of the range (0-indexed).
  • value: The number to be added to all elements within the range [left, right].
  • Returns: Nothing. Modifies the internal state.

queryMax(left: number, right: number): number

  • left: The starting index of the range (0-indexed).
  • right: The ending index of the range (0-indexed).
  • Returns: The maximum value in the specified range [left, right].

Clarifications

  • All indices (left, right) are 0-based and inclusive.
  • It is guaranteed that 0 <= left <= right < N for all updateRange and queryMax calls.
  • The value in updateRange can be positive, negative, or zero.
  • The initialArray will not be empty.

Examples

1

Example 1

Input:

operations = ["DynamicRangeMaximum","queryMax","updateRange","queryMax","queryMax","updateRange","queryMax"], params = [[[1,2,3,4,5]],[0,4],[0,2,10],[0,1],[0,4],[3,4,-5],[2,4]]

Output:

[null,5,null,12,13,null,13]

Note:

  1. Initialize with [1,2,3,4,5].
  2. queryMax(0,4): Max of [1,2,3,4,5] is 5.
  3. updateRange(0,2,10): Array becomes [11,12,13,4,5].
  4. queryMax(0,1): Max of [11,12] is 12.
  5. queryMax(0,4): Max of [11,12,13,4,5] is 13.
  6. updateRange(3,4,-5): Array becomes [11,12,13,-1,0].
  7. queryMax(2,4): Max of [13,-1,0] is 13.
2

Example 2

Input:

operations = ["DynamicRangeMaximum","updateRange","queryMax","updateRange","queryMax"], params = [[[10]],[0,0,-5],[0,0],[0,0,20],[0,0]]

Output:

[null,null,5,null,25]

Note:

  1. Initialize with [10].
  2. updateRange(0,0,-5): Array becomes [5].
  3. queryMax(0,0): Max of [5] is 5.
  4. updateRange(0,0,20): Array becomes [25].
  5. queryMax(0,0): Max of [25] is 25.
3

Example 3

Input:

operations = ["DynamicRangeMaximum","updateRange","queryMax","updateRange","queryMax"], params = [[[1,1,1,1,1]],[0,4,5],[0,2],[2,4,-2],[0,4]]

Output:

[null,null,6,null,6]

Note:

  1. Initialize with [1,1,1,1,1].
  2. updateRange(0,4,5): Array becomes [6,6,6,6,6].
  3. queryMax(0,2): Max of [6,6,6] is 6.
  4. updateRange(2,4,-2): Array becomes [6,6,4,4,4].
  5. queryMax(0,4): Max of [6,6,4,4,4] is 6.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (where N is the length of initialArray)
  • -10^9 <= initialArray[i] <= 10^9
  • -1000 <= value <= 1000 for updateRange operations
  • 1 <= Q <= 10^5 (where Q is the total number of updateRange and queryMax operations)
  • Expected time complexity for updateRange and queryMax operations: O(log N)
  • Expected space complexity: O(N)

Out of scope

  • Input validation for left, right indices (assume they are always valid).
  • Handling extremely large values that could cause integer overflow beyond standard number limits (assume number type is sufficient).

What interviewers evaluate

  • Correctness: The solution accurately computes maximums and applies updates across ranges.
  • Efficiency: The implementation adheres to the specified logarithmic time complexity for operations.
  • Data Structure Design: Proper construction and utilization of an appropriate data structure (e.g., Segment Tree).
  • Lazy Propagation: Effective implementation of lazy propagation to optimize range updates.
  • Code Quality: Clean, readable, and well-structured code.

Loading editor...