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 _thesum of all subarray ranges of _nums .

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
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] <= 10^9

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

Solution

Approach

For each subarray, the range is the difference between the maximum and minimum. Instead of brute force, we can count for each element how many subarrays it is the maximum and how many it is the minimum, and sum up their contributions. This can be done efficiently using monotonic stacks.

For each index, find the previous and next less/greater elements. The number of subarrays where nums[i] is the minimum is (i - prev_less) * (next_less - i), and similarly for maximum. The answer is the sum of all contributions as maximum minus the sum as minimum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        // Max contribution
        stack<int> st;
        for (int i = 0; i <= n; ++i) {
            while (!st.empty() && (i == n || nums[st.top()] < (i < n ? nums[i] : INT_MAX))) {
                int j = st.top(); st.pop();
                int k = st.empty() ? -1 : st.top();
                res += (long long)nums[j] * (j - k) * (i - j);
            }
            st.push(i);
        }
        // Min contribution
        st = stack<int>();
        for (int i = 0; i <= n; ++i) {
            while (!st.empty() && (i == n || nums[st.top()] > (i < n ? nums[i] : INT_MIN))) {
                int j = st.top(); st.pop();
                int k = st.empty() ? -1 : st.top();
                res -= (long long)nums[j] * (j - k) * (i - j);
            }
            st.push(i);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.*;
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long res = 0;
        Deque<Integer> st = new ArrayDeque<>();
        // Max contribution
        for (int i = 0; i <= n; ++i) {
            while (!st.isEmpty() && (i == n || nums[st.peek()] < (i < n ? nums[i] : Integer.MAX_VALUE))) {
                int j = st.pop();
                int k = st.isEmpty() ? -1 : st.peek();
                res += (long)nums[j] * (j - k) * (i - j);
            }
            st.push(i);
        }
        st.clear();
        // Min contribution
        for (int i = 0; i <= n; ++i) {
            while (!st.isEmpty() && (i == n || nums[st.peek()] > (i < n ? nums[i] : Integer.MIN_VALUE))) {
                int j = st.pop();
                int k = st.isEmpty() ? -1 : st.peek();
                res -= (long)nums[j] * (j - k) * (i - j);
            }
            st.push(i);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun subArrayRanges(nums: IntArray): Long {
        val n = nums.size
        var res = 0L
        val st = ArrayDeque<Int>()
        // Max contribution
        for (i in 0..n) {
            while (st.isNotEmpty() && (i == n || nums[st.last()] < if (i < n) nums[i] else Int.MAX_VALUE)) {
                val j = st.removeLast()
                val k = if (st.isEmpty()) -1 else st.last()
                res += nums[j].toLong() * (j - k) * (i - j)
            }
            st.addLast(i)
        }
        st.clear()
        // Min contribution
        for (i in 0..n) {
            while (st.isNotEmpty() && (i == n || nums[st.last()] > if (i < n) nums[i] else Int.MIN_VALUE)) {
                val j = st.removeLast()
                val k = if (st.isEmpty()) -1 else st.last()
                res -= nums[j].toLong() * (j - k) * (i - j)
            }
            st.addLast(i)
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def subArrayRanges(self, nums: list[int]) -> int:
        n = len(nums)
        res = 0
        st = []
        # Max contribution
        for i in range(n+1):
            while st and (i == n or nums[st[-1]] < (nums[i] if i < n else float('inf'))):
                j = st.pop()
                k = st[-1] if st else -1
                res += nums[j] * (j - k) * (i - j)
            st.append(i)
        st.clear()
        # Min contribution
        for i in range(n+1):
            while st and (i == n or nums[st[-1]] > (nums[i] if i < n else float('-inf'))):
                j = st.pop()
                k = st[-1] if st else -1
                res -= nums[j] * (j - k) * (i - j)
            st.append(i)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut res = 0i64;
        let mut st = Vec::new();
        // Max contribution
        for i in 0..=n {
            while let Some(&j) = st.last() {
                if i == n || nums[j] < if i < n { nums[i] } else { i32::MAX } {
                    st.pop();
                    let k = *st.last().unwrap_or(&-1);
                    res += nums[j] as i64 * (j as i64 - k as i64) * (i as i64 - j as i64);
                } else { break; }
            }
            st.push(i as i32);
        }
        st.clear();
        // Min contribution
        for i in 0..=n {
            while let Some(&j) = st.last() {
                if i == n || nums[j] > if i < n { nums[i] } else { i32::MIN } {
                    st.pop();
                    let k = *st.last().unwrap_or(&-1);
                    res -= nums[j] as i64 * (j as i64 - k as i64) * (i as i64 - j as i64);
                } else { break; }
            }
            st.push(i as i32);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function subArrayRanges(nums: number[]): number {
    const n = nums.length;
    let res = 0;
    const st: number[] = [];
    // Max contribution
    for (let i = 0; i <= n; ++i) {
        while (st.length && (i === n || nums[st[st.length-1]] < (i < n ? nums[i] : Infinity))) {
            const j = st.pop()!;
            const k = st.length ? st[st.length-1] : -1;
            res += nums[j] * (j - k) * (i - j);
        }
        st.push(i);
    }
    st.length = 0;
    // Min contribution
    for (let i = 0; i <= n; ++i) {
        while (st.length && (i === n || nums[st[st.length-1]] > (i < n ? nums[i] : -Infinity))) {
            const j = st.pop()!;
            const k = st.length ? st[st.length-1] : -1;
            res -= nums[j] * (j - k) * (i - j);
        }
        st.push(i);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)