# 2104. Sum of Subarray Ranges

![](/files/wd7TXve8vRC9F6pr2owp)

sum = sum(max) - sum(min) -> this is the point!

because nextLarger and prevLarger , prevSmaller, nextSmaller just help us find left bound , right bound 

for min, or for max

but we don't know the paired min max how to map to each other (from nextLarger and prevLarger , prevSmaller, nextSmaller

but we need to cal max - min in this subarray's max min pair

seems hard to use range

T: O(n)

S: O(n)

```java
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[] prevSmaller = new int[n];
        int[] nextSmaller = new int[n];
        int[] prevGreater = new int[n];
        int[] nextGreater = new int[n];
        
        Arrays.fill(nextSmaller, n);
        Arrays.fill(prevSmaller, -1);
        Arrays.fill(nextGreater, n);
        Arrays.fill(prevGreater, -1);
        
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                nextSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                prevSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                nextGreater[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                prevGreater[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        long result = 0L;
        
        // between nextGreater and prevGreater => max
        // between nextSmaller and prevSmaller => min
        // max - min
        for (int i = 0; i < n; i++) {
            result += (long)(nextGreater[i] - i)*(i - prevGreater[i])*nums[i] - (long)(nextSmaller[i] - i)*(i - prevSmaller[i])*nums[i];
        }
        
        return result;
    }
}

/*
range:
the difference between the largest and smallest element in the subarray.
return sum of all in this range

[1,2,3]

[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.

if nums[i] is min => the range: prevSmaller: l and nextSmaller; r
nums[i]*(i-l)*(r-i)

if nums[i] is max : b => the range: prevGreater and nextGreater
nums[i]*(i-l)*(r-i)

result += nums[i]*(i-l)*(r-i)
result -= nums[i]*(i-l)*(r-i)


nums[i]*(i-l)*(r-i)
-> 

(i-l)*(r-i)
i的左邊有幾個數
右邊有幾個數, 相乘起來就是總共個數

ex: 1,2,3
max:
nextLarger: [1, 2, 3]
prevLarger: [-1, -1, -1]

當i = 0, nums = 1
(r - i) * (i - l)
(1 - 0) * (0 -(-1)
-> 1*1 = 1

從這表也可以看出 max 1, 也只有一次
[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


舉例 num = 3來說, i = 2

nextLarger: [1, 2, 3]
prevLarger: [-1, -1, -1]

(3 - 2) * (2 - (-1))
= 1* 3 = 3
num = 3 也的確出現 max 3 次 (subarray 內出現 3次
      i
-1.   2. 3
 
*/
```

## more concise

```java
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        int[] nextSmaller = new int[n];
        int[] prevSmaller = new int[n];
        int[] nextLarger = new int[n];
        int[] prevLarger = new int[n];
        
        Arrays.fill(nextSmaller, n);
        Arrays.fill(nextLarger, n);
        Arrays.fill(prevSmaller, -1);
        Arrays.fill(prevLarger, -1);
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        // nextSmaller ： [3,1,2]
        /*
          (then 1 , has nextSmaller , record it! ->nextSmaller[0] = 1 , then pop
        0 (3  
        */
        for (int i = 0; i < n ; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                nextSmaller[stack.peek()] = i; 
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        // prevSmaller, avoid duplicate , we want left one, so when new number == stack number, we keep record it
        for (int i = n-1; i >= 0 ; i--) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                prevSmaller[stack.peek()] = i; 
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        // nextLarger
        for (int i = 0; i < n ; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                nextLarger[stack.peek()] = i; 
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        // prevLarger, avoid duplicate , we want left one, so when new number == stack number, we keep record it
        for (int i = n-1; i >= 0 ; i--) {
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                prevLarger[stack.peek()] = i; 
                stack.pop();
            }
            stack.push(i);
        }
        
        long result = 0L;
        for (int i = 0; i < n; i++) { // notice the long tupe
            result += (long)nums[i]*(nextLarger[i] - i)*(i - prevLarger[i]) - (long)nums[i]*(nextSmaller[i] - i)*(i - prevSmaller[i]);
        }
        return result;
    }
}

/*
1. brute force
find all subarrays, T: o(n^2), count of subarray -> T: O(n^2), find max, min, -> T: O(n^2*n) -> O(n^3)

2. how to avoid find all subarray

think of each elemnt as the min -> find the left, right bound. it means 
ex: [1,2,3]

1 as min -> [1,2,3] ->with this range, all subarrays' min is 1
...

how to find right bound?
use monostack find
nextSmaller [n, n, n] -> this array we will record each emlent's next smaller [n, n, n]

find left bound
prevSmaller [-1, -1, -1] -> this array we will record each emlent's prev smaller, from end [-1, 0, 1]
(index -> 3's next prev smaller num , index is 1 (nums[1] = 2) )
[n, n, n]
[-1, 0, 1]


for index 0 (1) -> range is -1 to n (以 num 1 為 min 的index範圍) -> [1,2,3] -> in these subarrays (3 subarrays), the min is 1 -> sum(min of these subarrays) => 3*1= 3
-1 0 1 2  n
  [1,2,3]

for index 1 (2) -> range is 0 to n (以 num 2 為 min 的index範圍)-> [2,3] (2 subarrays), min is 2, 2*2=4
   0 1 2  n
  [1,2,3]. range (0 to n) -> 就是 index 1, 2 -> [2, 3]

for index 2 (3) -> range is 1 to n (以 num 3 為 min 的index範圍)-> [3] (1 subarray), min is 3, 3*1 = 3
     1 2  n
  [1,2,3]. range (1 to n) -> 就是 index 2 -> [3]

sum them up -> all min sum = 10

in example,
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

-> min: 1 出現了 3 次, 2 出現 2 次, 3 出現 1次, 跟我們前面的計算相符

we can see, actually, the ans is sum(max) - sum(min) -> we don't need to cal diff in each subarray

so we cal the sum(max)

result = sum(max) - sum(min) 


T: O(n)

duplicate case, 
why duplicate case will cause error?
[5,3,3,3,6]
   ^ ^ ^
these 3's range are same , so 3 subarrays are the same

  我們可以約定最右邊的重複是我們要的最小值  
   

在 nextSmaller 我們不管  [1,3,3,3,2] => index 1's 3 is min the  range is

we handle this in prevSmaller
[]

[1,3,3,3,1]

[-1,-1,-1,-1,-1]

find left bound if smaller or equal -> we find the left bound

for this 3
[1,3,3,3,1]
       ^
     f  -> here we find the left bound

like this
[1,3,3,[3,1]]
     

index 2 3 ->equal!!

index 3 3 -> record prevSmaller[3] = 2 
index 4 1

*/ja




```

![](/files/H9iwcB17rLpnIWZEA310)

## duplicate case

```
duplicate case, 
why duplicate case will cause error?
[5,3,3,3,6]
   ^ ^ ^
these 3's range are same , so 3 subarrays are the same

  我們可以約定最右邊的重複是我們要的最小值  
   
所以 3 [8 4 4 8 4]
               ＾
這個最右邊的 4會是我們的 right bound
left bound 就可以有4的重複 所以可以一路到 8

但 right bound 就不行再有重複了

     3 [8 4 4 8 4] 4                           
                ^
 所以像這樣 right bound 就是到 ^ 這裡
 
 所以 left bound 我們可以 <=
 但 right bound 是 <
 
 ----------------
 
 再回到回本的來看
 [8 4 4 8 4]
 => 如果不處理 以 4為min去找時, 這裡就會有三個一樣的 subarray 都是 [8 4 4 8 4]
 
 所以約定最右邊的 4 是我們要的, left bound <=, right bound <
 
 所以 看 index 1 的4時(第1個4)
  [8 4 4 8 4]
  => 會是 [8,4]
  
  看 index 2 的4時(第2個4)
  [8 4 4 8 4]
  => 會是 [4]
  
  看 index 3 的4時 (第3個4)
  [8 4 4 8 4]
  => 會是 [8 4 4 8 4]
  
  如此就可以解決重複的問題！
 
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/2104.-sum-of-subarray-ranges.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.