Stock Market Range Minimum Query using Segment Tree
Filed under Amazon
Free read 2 of 3Confirm if updates are point updates or range updates, and whether deletions/insertions dynamically resize the array.
The question
Design a data structure to maintain stock values over various periods and return the minimum stock value over a given query range, implementing a segment tree to support range minimum queries and point updates.
Constraints
- Array size n up to 10^5.
- Operations include point updates and range minimum queries.
Examples
- Input
- arr = [5, 2, 6, 3, 9, 1], query(1, 4)
- Output
- 2
- Why
- The minimum value in the range index 1 to 4 is 2.
Approach
Confirm if updates are point updates or range updates, and whether deletions/insertions dynamically resize the array.
Iterate through the specified range for every query taking O(n) time per query.
Use a segment tree to achieve O(log n) time complexity for both range minimum queries and point updates.
Single element array, identical stock values, and out-of-bound queries.
Tips
- What they are testing: Test range queries covering single elements, entire array, and updates at boundary indices 0 and n-1.
- Common mistake: Incorrect segment tree index calculations or failing to properly propagate updates up the tree.
Follow-ups
- How would you update the segment tree by deleting an old stock value and inserting a new one for a 6-month period in better than O(n) time?
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.