Problem Statement

Given an integer array nums, determine the range of a subarray, defined as the difference between the largest and smallest elements within the subarray. Calculate and return the sum of all subarray ranges of nums.

A subarray is defined as a contiguous, non-empty sequence of elements within the array.

Examples

Example 1:

Input: nums = [1, 2, 3]
Output: 4

Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1-1 = 0
[2], range = 2-2 = 0
[3], range = 3-3 = 0
[1, 2], range = 2-1 = 1
[2, 3], range = 3-2 = 1
[1, 2, 3], range = 3-1 = 2
So, the sum of all ranges is 0 + 0 + 1 + 1 + 2 = 4

Example 2:

Input: nums = [1, 3, 3]
Output: 4

Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[3], range = 3 - 3 = 0
[3], range = 3 - 3 = 0
[1,3], range = 3 - 1 = 2
[3,3], range = 3 - 3 = 0
[1,3,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The brute force way to solve this problem is by generating all the subarrays and finding the minimum and maximum values in all of them. The range of a subarray can be found as the difference between the maximum and minimum value which can be summed up for all the subarrays to get the result.

Approach:

1. Initialize a variable to store the required sum with 0 initially.
2. Traverse on the array. Initialize two variables to store the minimum and maximum elements in the subarray.
3. Use a nested loop to traverse all the subarrays and find the minimum and maximum of each subarray. Update the sum for each subarray by finding the range of subarray (maximum-minimum).
4. Once all the subarrays are taken into consideration, the result will be stored in the sum variable.

Code:

class Solution {
public:
    long long subArrayRanges(vector<int> &nums) {
        long long sum = 0;

        // Outer loop: iterate over all starting points of subarrays
        for (int i = 0; i < nums.size(); i++) {
            int mini = INT_MAX;  // initialize minimum for the current subarray
            int maxi = INT_MIN;  // initialize maximum for the current subarray

            // Inner loop: extend the subarray from i to j
            for (int j = i; j < nums.size(); j++) {
                // Update the minimum and maximum values in the current subarray [i..j]
                mini = min(mini, nums[j]);
                maxi = max(maxi, nums[j]);

                // The range of current subarray is max - min
                // Add this range to the total sum
                sum = sum + (maxi - mini);
            }
        }

        // Return the total of all subarray ranges
        return sum;
    }
};

Complexity Analysis:

• Time Complexity:O(N^2) (where N is the size of the array)
  • Using two nested loops.
• Space Complexity:O(1)
  • Using only a couple of variables.

2️⃣ Monotonic Stack

To optimally find the sum of largest and the smallest elements in the array, the concept of Next/Previous Smaller/Greater Elements come into picture as discussed in the Sum of Subarray minimums (Optimal Solution).

Approach:

1. Four helper functions are used to find specific indices:
   1. Next Smaller Elements (NSE): For each element, find the index of the next smaller element to its right.
   2. Next Greater Elements (NGE): For each element, find the index of the next greater element to its right.
   3. Previous Smaller or Equal Elements (PSEE): For each element, find the index of the previous smaller or equal element to its left.
   4. Previous Greater or Equal Elements (PGEE): For each element, find the index of the previous greater or equal element to its left.
2. Utilize the NSE and PSEE indices to calculate the sum of the minimum values in all subarrays. Utilize the NGE and PGEE indices to calculate the sum of the maximum values in all subarrays.
3. The final result is obtained by subtracting the sum of subarray minimums from the sum of subarray maximums. This gives the sum of ranges of all subarrays.

Code:

#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];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the smaller element */
            while(!st.empty() && arr[st.top()] >= currEle){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : n;
            
            /* Push the index of current 
            element in 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];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the greater element */
            while(!st.empty() && arr[st.top()] <= currEle){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : n;
            
            /* Push the index of current 
            element in 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];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            elements are greater than the current element */
            while(!st.empty() && arr[st.top()] > currEle){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : -1;
            
            /* Push the index of current 
            element in 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
        for(int i=0; i < n; i++) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            elements are smaller than the current element */
            while(!st.empty() && arr[st.top()] < currEle){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : -1;
            
            /* Push the index of current 
            element in the stack */
            st.push(i);
        }
        
        // Return the answer
        return ans;
    }
    
    /* Function to find the sum of the 
    minimum value in each subarray */
    long long sumSubarrayMins(vector<int> &arr) {
        
        vector<int> nse = findNSE(arr);
        
        vector<int> psee = findPSEE(arr);
        
        // Size of array
        int n = arr.size();
        
        // To store the sum
        long long sum = 0;
        
        // Traverse on the array
        for(int i=0; i < n; i++) {
            
            // Count of first type of subarrays
            int left = i - psee[i];
            
            // Count of second type of subarrays
            int right = nse[i] - i;
            
            /* Count of subarrays where 
            current element is minimum */
            long long freq = left*right*1LL;
            
            // Contribution due to current element 
            long long val = (freq*arr[i]*1LL);
            
            // Updating the sum
            sum += val;
        }
        
        // Return the computed sum
        return sum;
    }
    
    /* Function to find the sum of the 
    maximum value in each subarray */
    long long sumSubarrayMaxs(vector<int> &arr) {
        
        vector<int> nge = findNGE(arr);
        
        vector<int> pgee = findPGEE(arr);
        
        // Size of array
        int n = arr.size();
        
        // To store the sum
        long long sum = 0;
        
        // Traverse on the array
        for(int i=0; i < n; i++) {
            
            // Count of first type of subarrays
            int left = i - pgee[i];
            
            // Count of second type of subarrays
            int right = nge[i] - i;
            
            /* Count of subarrays where 
            current element is minimum */
            long long freq = left*right*1LL;
            
            // Contribution due to current element 
            long long val = (freq*arr[i]*1LL);
            
            // Updating the sum
            sum += val;
        }
        
        // Return the computed sum
        return sum;
    }
    
public:
    /* Function to find the sum of 
    subarray ranges in each subarray */
    long long subArrayRanges(vector<int> &arr) {
        
        // Return the result
        return ( sumSubarrayMaxs(arr) - 
                 sumSubarrayMins(arr) );
    }
};

int main() {
    vector<int> arr = {1, 2, 3};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the sum of 
    subarray ranges in each subarray */
    long long ans = sol.subArrayRanges(arr);
    
    cout << "The sum of subarray ranges is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the size of given array)
  • Calculating the sum of subarray maximums takes O(N) time.
  • Calculating the sum of subarray minimums takes O(N) time.
• Space Complexity:O(N)
  • Calculating the sum of subarray maximums requires O(N) space.
  • Calculating the sum of subarray minimums requires O(N) space.