Given an integer array nums, define the range of a non-empty contiguous subarray as the maximum element minus the minimum element. Return the sum of the ranges of all non-empty contiguous subarrays.
Example 1
Input: nums = [1, 2, 3]
Output: 4
Explanation: The subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].
Their corresponding ranges are 0, 0, 0, 1, 1, and 2.
The sum of all subarray ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.
Example 2
Input: nums = [5]
Output: 0
Explanation: The only subarray is [5].
Its range is 5 - 5 = 0 because the maximum and minimum values are equal.
The sum of all subarray ranges is 0.
Brute Force Approach
Every subarray range is the difference between its largest and smallest values. Instead of checking each subarray again from the beginning, choose one starting index and keep extending the ending index toward the right.
While extending, maintain the smallest and largest values found so far. Each new ending index creates one new subarray, so its range can be calculated immediately. This avoids an extra scan, although two nested loops are still needed to visit every subarray.
Algorithm
Initialize
answer = 0to store the sum of the ranges of all subarrays.Select every array index as the starting position of a subarray.
Set
currentMinimumandcurrentMaximumto the starting value, because the first subarray contains only that element.Extend the ending index from the starting position to the end of the array, so every subarray with the selected start is generated.
Update
currentMinimumwith the smaller value andcurrentMaximumwith the larger value after including each new element.Add
currentMaximum - currentMinimumtoanswer, because this difference is the range of the current subarray.Return
answerafter processing every possible starting and ending index pair.
Dry Run
sum-of-subarray-ranges-brute-force-palette-corrected.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the sum of every subarray range. long long subArrayRanges(vector<int>& nums) { // Store the accumulated range sum. long long answer = 0; // Choose every possible starting index. for (int start = 0; start < nums.size(); start++) { // Track extrema for the growing subarray. int minimum = nums[start]; int maximum = nums[start]; // Extend the current subarray to the right. for (int end = start; end < nums.size(); end++) { // Include the new value in both extrema. minimum = min(minimum, nums[end]); maximum = max(maximum, nums[end]); // Add the range of the current subarray. answer += (long long)maximum - minimum; } } // Return the sum after every pair is visited. return answer; }};// Driver codeint main() { vector<int> nums = {1, 2, 3}; Solution obj; cout << obj.subArrayRanges(nums) << endl; return 0;}Note: The brute-force approach may fail for large input values. Quadratic work can cause an online judge to report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N2), where N is the number of elements, because every possible start and end index pair is visited once.
Space Complexity: O(1), because only the answer and the running minimum and maximum values are stored.
Optimal Approach
The key idea is to break the range of every subarray into two separate contributions: maximum − minimum. This means we can first calculate the sum of all subarray maximums and the sum of all subarray minimums, then subtract the latter from the former. This is similar to the contribution-based technique used in Sum of Subarray Minimums.
Instead of generating every subarray, consider each element and count how many subarrays use it as the maximum or minimum. Monotonic stacks help find the nearest elements that can stop its contribution on the left and right. We use strict comparison on one side and non-strict comparison on the other so that duplicate values are assigned consistently and no subarray is counted more than once.
Algorithm
Create four boundary arrays to store the previous and next smaller and greater indices for every element.
Traverse from left to right using monotonic stacks to find the previous smaller-or-equal and previous greater-or-equal boundaries.
Remove equal values from the stacks while finding previous boundaries, so duplicate elements are handled consistently.
Clear both stacks and traverse from right to left to find the next smaller and next greater boundaries.
Keep equal values while finding next boundaries, completing the strict/non-strict comparison pattern needed to avoid duplicate counting.
For each index, calculate the number of possible left and right boundaries using its distances from the corresponding smaller and greater elements.
Calculate the element's contribution as a maximum using its greater boundaries and add it to the answer.
Calculate the element's contribution as a minimum using its smaller boundaries and subtract it from the answer.
Return
answer, which now contains the sum of all subarray maximums minus the sum of all subarray minimums.
Dry Run
sum-of-subarray-ranges-optimal-palette-corrected.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to find the indices of next smaller elements. vector<int> findNSE(vector<int> &arr) { // Size of array. int n = arr.size(); // To store the answer. vector<int> ans(n); // Stack. stack<int> st; // Start traversing from the back. for(int i = n - 1; i >= 0; i--) { // Get the current element. int currEle = arr[i]; // Remove elements that are not smaller. while(!st.empty() && arr[st.top()] >= currEle) { st.pop(); } // Store the next smaller element index. ans[i] = !st.empty() ? st.top() : n; // Push the current index into the stack. st.push(i); } // Return the answer. return ans; } // Function to find the indices of next greater elements. vector<int> findNGE(vector<int> &arr) { // Size of array. int n = arr.size(); // To store the answer. vector<int> ans(n); // Stack. stack<int> st; // Start traversing from the back. for(int i = n - 1; i >= 0; i--) { // Get the current element. int currEle = arr[i]; // Remove elements that are not greater. while(!st.empty() && arr[st.top()] <= currEle) { st.pop(); } // Store the next greater element index. ans[i] = !st.empty() ? st.top() : n; // Push the current index into the stack. st.push(i); } // Return the answer. return ans; } // Function to find the indices of previous smaller or equal elements. vector<int> findPSEE(vector<int> &arr) { // Size of array. int n = arr.size(); // To store the answer. vector<int> ans(n); // Stack. stack<int> st; // Traverse on the array. for(int i = 0; i < n; i++) { // Get the current element. int currEle = arr[i]; // Remove elements that are greater. while(!st.empty() && arr[st.top()] > currEle) { st.pop(); } // Store the previous smaller or equal index. ans[i] = !st.empty() ? st.top() : -1; // Push the current index into the stack. st.push(i); } // Return the answer. return ans; } // Function to find the indices of previous greater or equal elements. vector<int> findPGEE(vector<int> &arr) { // Size of array. int n = arr.size(); // To store the answer. vector<int> ans(n); // Stack. stack<int> st; // Traverse on the array.Complexity Analysis
Time Complexity: O(9N) = O(N), where N is the number of elements. The four monotonic-stack traversals each perform at most 2N push/pop operations, and the final contribution calculation takes O(N).
Space Complexity: O(5N) = O(N), because four boundary arrays and the monotonic stack can each store up to N indices.
Interview follow-up Questions
A single value is both the maximum and minimum of its subarray. Therefore, the subarray range is maximum - minimum = 0.
Be the first to add a comment.