# Sum of Subarray Ranges
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-subarray-ranges)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-subarray-ranges
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [TikTok](https://scaleengineer.com/companies/tiktok)
---
## Problem
You are given an integer array `nums`. The **range** of a subarray of `nums` is the difference between the largest and smallest element in the subarray.

Return _the **sum of all** subarray ranges of_ `nums`_._

A subarray is a contiguous **non-empty** sequence of elements within an array.

**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 + 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.

**Example 3:**

**Input:** nums = [4,-2,-3,4,1]
**Output:** 59
**Explanation:** The sum of all subarray ranges of nums is 59.

**Constraints:**

* `1 <= nums.length <= 1000`
* `-109 <= nums[i] <= 109`

**Follow-up:** Could you find a solution with `O(n)` time complexity?

# Approaches
## Nested Loops Iteration
This approach iterates through all possible subarrays using nested loops. For each subarray, it keeps track of the minimum and maximum elements found so far and calculates the range. The sum of these ranges gives the final answer.
**Time:** O(n^2) where `n` is the number of elements in `nums`. The two nested loops result in a quadratic time complexity. The outer loop runs `n` times, and the inner loop runs on average `n/2` times. · **Space:** O(1) because we only use a constant amount of extra space for variables like `totalRangeSum`, `minVal`, and `maxVal`.
**Pros:** Simple to understand and implement.; Requires no extra space apart from a few variables.
**Cons:** Less efficient than the optimal solution.; For larger constraints on `n`, this approach would be too slow and result in a Time Limit Exceeded error.
### Explanation
The most straightforward way to solve this problem is to generate every possible contiguous subarray, find the minimum and maximum value within each, calculate the range, and sum up all the ranges.

We can use two nested loops to define the start and end of each subarray. The outer loop with index `i` iterates from `0` to `n-1`, fixing the starting point of the subarrays. The inner loop with index `j` iterates from `i` to `n-1`, extending the subarray to the right. For each subarray starting at `i`, we maintain two variables, `currentMin` and `currentMax`. As the inner loop progresses from `j = i` to `n-1`, we consider the subarray `nums[i...j]`. We update `currentMin` and `currentMax` with `nums[j]`. The range for the subarray `nums[i...j]` is `currentMax - currentMin`, which we add to a running total. After both loops complete, this total sum is our answer.

```java
class Solution {
    public long subarrayRanges(int[] nums) {
        long totalRangeSum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int minVal = nums[i];
            int maxVal = nums[i];
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, nums[j]);
                maxVal = Math.max(maxVal, nums[j]);
                totalRangeSum += (long) maxVal - minVal;
            }
        }
        return totalRangeSum;
    }
}
```
### Algorithm
1. Initialize a variable `totalRangeSum` to 0.
2. Iterate through the array with an index `i` from 0 to `n-1`. This index `i` will be the starting point of our subarrays.
3. Inside this loop, initialize `minVal = nums[i]` and `maxVal = nums[i]`.
4. Start a nested loop with an index `j` from `i` to `n-1`. This index `j` will be the ending point of our subarrays.
5. In the inner loop, for each subarray `nums[i...j]`, update the `minVal` and `maxVal` by comparing with the current element `nums[j]`.
   - `minVal = Math.min(minVal, nums[j])`
   - `maxVal = Math.max(maxVal, nums[j])`
6. Calculate the range for the current subarray `nums[i...j]` as `maxVal - minVal`.
7. Add this range to the `totalRangeSum`.
8. After the loops complete, `totalRangeSum` will hold the sum of all subarray ranges. Return this value.

## Monotonic Stack
This optimal approach solves the problem in linear time by reformulating it. The sum of all subarray ranges, `Sum(max - min)`, is equivalent to `Sum(max) - Sum(min)`. We can calculate the sum of maximums and the sum of minimums for all subarrays separately. A monotonic stack is a key data structure used to efficiently determine, for each element `nums[i]`, the number of subarrays where it serves as the maximum or minimum.
**Time:** O(n). Each index is pushed onto and popped from the stack at most once for each of the two main loops (one for sum of maxes, one for sum of mins). Thus, the total time complexity is linear with respect to the input size. · **Space:** O(n) in the worst case. The stack can store up to `n` indices if the input array is, for example, strictly increasing (for sum of mins) or strictly decreasing (for sum of maxs).
**Pros:** Highly efficient with linear time complexity, making it the optimal solution.; Satisfies the follow-up question for an O(n) solution.
**Cons:** More complex to understand and implement correctly compared to the O(n^2) approach.; The logic for handling boundaries and duplicates with the monotonic stack can be subtle and error-prone.
### Explanation
This approach is based on a clever observation: the sum of ranges of all subarrays can be split into two independent problems: `(sum of all subarray maximums) - (sum of all subarray minimums)`.

We can calculate these two sums separately. For each element `nums[i]`, we find its total contribution to `sumOfMaxs` and `sumOfMins`. The contribution is `nums[i]` multiplied by the number of subarrays where it is the maximum (or minimum).

To count these subarrays accurately, especially when duplicate values exist, we must establish a consistent rule to avoid overcounting. For instance, we can decide that `nums[i]` is the designated maximum of a subarray only if it's the *last* occurrence of that value within that subarray. This means we need to find the boundaries `(left, right)` for `nums[i]` such that all elements between `left` and `i` are less than or equal to `nums[i]`, and all elements between `i` and `right` are strictly less than `nums[i]`.

A monotonic stack is the perfect tool for finding these boundaries for every element in `O(n)` time. We use one pass with a monotonic stack to calculate `sumOfMaxs` and another pass to calculate `sumOfMins`.

For `sumOfMaxs`, we maintain a stack of indices in decreasing order of their values in `nums`. When we encounter an element `nums[i]` that is greater than the element at the top of the stack, we know `nums[i]` is the 'next greater element' for the popped element. This allows us to determine the boundaries and calculate the contribution on the fly.

```java
import java.util.Stack;

class Solution {
    public long subarrayRanges(int[] nums) {
        int n = nums.length;
        long sumOfMaxs = 0;
        long sumOfMins = 0;
        Stack<Integer> stack = new Stack<>();

        // Calculate sum of maximums of all subarrays
        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() && (i == n || nums[stack.peek()] <= nums[i])) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                int right = i;
                sumOfMaxs += (long) nums[mid] * (mid - left) * (right - mid);
            }
            if (i < n) {
                stack.push(i);
            }
        }

        stack.clear();

        // Calculate sum of minimums of all subarrays
        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() && (i == n || nums[stack.peek()] >= nums[i])) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                int right = i;
                sumOfMins += (long) nums[mid] * (mid - left) * (right - mid);
            }
            if (i < n) {
                stack.push(i);
            }
        }

        return sumOfMaxs - sumOfMins;
    }
}
```
### Algorithm
1. The core idea is that `Sum(max(subarray) - min(subarray))` equals `Sum(max(subarray)) - Sum(min(subarray))`.
2. We calculate `sumOfMaxs` (sum of maximums of all subarrays) and `sumOfMins` (sum of minimums of all subarrays) separately.
3. To calculate `sumOfMaxs`:
   a. Initialize an empty stack and `sumOfMaxs = 0`.
   b. Iterate with an index `i` from `0` to `n` (inclusive, to handle elements remaining in the stack).
   c. While the stack is not empty and the element at the top of the stack is less than or equal to the current element (`i == n` or `nums[stack.peek()] <= nums[i]`):
      i. Pop an index `mid` from the stack. This `nums[mid]` is a local maximum.
      ii. The left boundary for its subarrays is the index at the new top of the stack (or -1 if empty).
      iii. The right boundary is the current index `i`.
      iv. The number of subarrays where `nums[mid]` is the maximum is `(mid - left) * (i - mid)`.
      v. Add `(long)nums[mid] * (mid - left) * (i - mid)` to `sumOfMaxs`.
   d. If `i < n`, push `i` onto the stack.
4. To calculate `sumOfMins`, repeat step 3 but with the comparison reversed: while the stack is not empty and `nums[stack.peek()] >= nums[i]`.
5. The final result is `sumOfMaxs - sumOfMins`.

# Solutions
### Java

```java
class Solution {
public
  long subArrayRanges(int[] nums) {
    long ans = 0;
    int n = nums.length;
    for (int i = 0; i < n - 1; ++i) {
      int mi = nums[i], mx = nums[i];
      for (int j = i + 1; j < n; ++j) {
        mi = Math.min(mi, nums[j]);
        mx = Math.max(mx, nums[j]);
        ans += (mx - mi);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long subArrayRanges(vector<int> &nums) {
    long long ans = 0;
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i) {
      int mi = nums[i], mx = nums[i];
      for (int j = i + 1; j < n; ++j) {
        mi = min(mi, nums[j]);
        mx = max(mx, nums[j]);
        ans += (mx - mi);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def subArrayRanges(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(n - 1): mi = mx = nums[i] for j in range(i + 1, n): mi = min(mi, nums[j]) mx = max(mx, nums[j]) ans += mx - mi return ans

```