MaxSubarrayAmplitude — Problem Statement & Solution Guide
Problem Description
Given a 0-indexed integer array nums and two integer indices left and right, determine the maximum amplitude of any contiguous subarray that lies entirely within the index range [left, right]. The amplitude of a subarray is defined as the difference between its maximum element and its minimum element. Your task is to compute this maximum difference across all possible contiguous subarrays starting at or after left and ending at or before right.
The input consists of the array nums, the starting index left, and the ending index right. The output should be a single integer representing the largest amplitude found. Note that a subarray of length 1 has an amplitude of 0, as its maximum and minimum elements are identical.
DSA Pattern Breakdown
DSA Pattern Breakdown
"MaxSubarrayAmplitude"
WHY DOES IT MATTER?
Range‑query patterns (max/min, sum, gcd, etc.) appear in almost every performance‑critical system, from analytics dashboards to real‑time monitoring. Mastering them lets you turn brute‑force scans into logarithmic or constant‑time answers, dramatically reducing latency and cost.
OPTIMIZATION CHALLENGE
The insight is to decouple the two aggregates (max and min) and store them together in a hierarchical data structure. This enables answering both in a single traversal of O(log n) nodes, cutting the naïve O(length) scan out of the query path.
REAL-WORLD CONNECTION
Think of a distributed log‑processing pipeline where each shard stores summary statistics (max latency, min latency) for its segment. When a dashboard asks for the latency spread over a time window, the system merges the pre‑computed summaries instead of re‑scanning every event.
During an interview, build the segment tree skeleton first (build, query, update) and then plug in the pair (max, min). Keep the code modular – a helper that merges two child pairs makes the logic error‑free and easy to explain.
COMPLEXITY AT A GLANCE
O(log n) per query (O(1) with Sparse Table)O(n)Core Theory — Why This Approach?
The amplitude of a subarray is simply the difference between its maximum and minimum values. For any interval [L, R] the subarray that stretches from the position of the global minimum to the position of the global maximum (or vice‑versa) is contiguous, so the maximum possible amplitude inside the interval is just max(nums[L..R]) − min(nums[L..R]). A naïve solution enumerates every possible subarray, computes its min and max, and keeps the best difference, leading to O(n²) time for a single query and O(n³) if many queries are asked – infeasible for n up to 10⁵ or more. The optimal paradigm treats the problem as a range‑query for two orthogonal aggregates (maximum and minimum). By preprocessing the array with a segment tree (or a Sparse Table for static data) that stores both the local max and min for each node, each query can be answered in O(log n) (or O(1) with Sparse Table) while using O(n) extra space. This reduction from quadratic to logarithmic time is the key to scaling the solution.
Interview Questions on This Problem
Q1How would you modify the solution if the array is mutable and you need to support point updates between queries?
Use a segment tree (or Fenwick tree variant) where each node stores a pair (max, min). Point updates modify the leaf and propagate changes up, preserving O(log n) query and update time.
Q2Can you solve the problem in O(1) per query after preprocessing? Under what constraints?
Yes, if the array is static (no updates) you can build two Sparse Tables – one for range maximum and one for range minimum – in O(n log n) time. Each query then answers max and min in O(1) using the overlapping intervals technique.
Q3Why does the maximum amplitude always equal the difference between the global max and min of the query range, regardless of the order of elements?
Because any two positions i ≤ j inside the range can be covered by the contiguous subarray nums[i..j]. Therefore the subarray that includes both the overall maximum and minimum of the range is valid, and its amplitude equals max − min, which is the upper bound for any subarray.
Examples
Input
nums = [3, 1, 4, 1, 5, 9, 2, 6], left = 1, right = 5
Output
8
Explanation: The subarray within indices [1, 5] is [1, 4, 1, 5, 9]. We examine all contiguous subarrays within this range. The subarray [1, 4, 1, 5, 9] has a maximum of 9 and a minimum of 1, yielding an amplitude of 9 - 1 = 8. Other subarrays like [4, 1, 5] have amplitude 4, and [1, 5, 9] have amplitude 8. The maximum amplitude observed is 8.
Input
nums = [10, 20, 30, 40, 50], left = 0, right = 4
Output
40
Explanation: The entire range [0, 4] is considered. The subarray [10, 20, 30, 40, 50] has a maximum of 50 and a minimum of 10. The amplitude is 50 - 10 = 40. Since the array is strictly increasing, the full range yields the maximum possible difference.
Input
nums = [5, 5, 5, 5], left = 1, right = 2
Output
0
Explanation: The subarray within indices [1, 2] is [5, 5]. The maximum element is 5 and the minimum element is 5. The amplitude is 5 - 5 = 0. All subarrays in this range consist of identical values, so the maximum amplitude is 0.
Input
nums = [-1, -5, -3, -8, -2], left = 0, right = 3
Output
7
Explanation: The subarray within indices [0, 3] is [-1, -5, -3, -8]. The maximum element is -1 and the minimum element is -8. The amplitude is -1 - (-8) = 7. This is the largest difference between any max and min in any contiguous subarray within the specified range.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= left <= right < nums.length
- The answer is guaranteed to fit in a 32-bit integer.
Optimal Approach & Strategy
Preprocess the array with a segment tree (or Sparse Table) that stores both max and min for each node. Answer each query by retrieving the max and min of the interval in O(log n) (or O(1) for static data) and return their difference.
Brute Force Approach
Enumerate every possible contiguous subarray inside [left,right], compute its min and max, and keep the largest difference. This requires O((right‑left)²) time.
Verified Code Solutions
function maxSubarrayAmplitude(nums, left, right) {
let maxVal = nums[left];
let minVal = nums[left];
for (let i = left + 1; i <= right; i++) {
if (nums[i] > maxVal) maxVal = nums[i];
if (nums[i] < minVal) minVal = nums[i];
}
return maxVal - minVal;
}#include <vector>
#include <algorithm>
class Solution {
public:
int maxSubarrayAmplitude(const std::vector<int>& nums, int left, int right) {
int maxVal = nums[left];
int minVal = nums[left];
for (int i = left + 1; i <= right; ++i) {
maxVal = std::max(maxVal, nums[i]);
minVal = std::min(minVal, nums[i]);
}
return maxVal - minVal;
}
};class Solution {
public int maxSubarrayAmplitude(int[] nums, int left, int right) {
int maxVal = nums[left];
int minVal = nums[left];
for (int i = left + 1; i <= right; i++) {
if (nums[i] > maxVal) maxVal = nums[i];
if (nums[i] < minVal) minVal = nums[i];
}
return maxVal - minVal;
}
}def maxSubarrayAmplitude(nums: list[int], left: int, right: int) -> int:
sub = nums[left:right + 1]
return max(sub) - min(sub)function maxSubarrayAmplitude(nums, left, right) {
let maxVal = nums[left];
let minVal = nums[left];
for (let i = left + 1; i <= right; i++) {
if (nums[i] > maxVal) maxVal = nums[i];
if (nums[i] < minVal) minVal = nums[i];
}
return maxVal - minVal;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.