#2104

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Sum of Subarray Ranges

Compute the total sum of ranges for all contiguous subarrays efficiently using stack-based state management techniques.

Problem Statement

Given an integer array nums, define the range of a subarray as the difference between its largest and smallest elements. A subarray is any contiguous sequence of elements within nums. Compute the sum of ranges for every possible subarray in nums.

Return the total sum of all subarray ranges. Your solution should handle arrays with up to 1000 elements and values ranging from -10^9 to 10^9, emphasizing efficient computation via stack-based state tracking for max and min elements.

Examples

Example 1

Input: nums = [1,2,3]

Output: 4

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

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

The sum of all subarray ranges of nums is 59.

Constraints

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

Solution Approach

Use Monotonic Stacks for Min/Max

Maintain two monotonic stacks: one increasing for tracking minimums and one decreasing for maximums. For each element, find the previous and next smaller and greater elements. This identifies the number of subarrays where the current element is the min or max.

Compute Contributions per Element

Calculate each element's contribution to the total sum by multiplying the number of subarrays where it is maximum by its value, and subtracting the number where it is minimum. Summing these contributions yields the final result without explicitly enumerating all subarrays.

Aggregate in Linear Time

Iterate over the array once, applying the monotonic stack logic for both min and max simultaneously. This allows O(n) computation with O(n) space, efficiently handling all subarray ranges while avoiding nested loops.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is pushed and popped at most once from each stack. Space complexity is O(n) for the stacks tracking previous and next smaller or greater elements.

What Interviewers Usually Probe

Expect candidates to recognize the pattern of using monotonic stacks for range-based subarray calculations.
Look for attempts to reduce nested loops by tracking element contributions to multiple subarrays.
Candidates should discuss edge cases where elements repeat and correctly handle inclusive counting of subarrays.

Common Pitfalls or Variants

Common pitfalls

Miscounting subarrays by not correctly combining previous and next smaller/greater indices.
Using nested loops leading to O(n^2) complexity, which fails for large arrays.
Failing to handle duplicates, causing overcounting or undercounting in contribution calculations.

Follow-up variants

Compute sum of subarray maximums only, emphasizing the same monotonic stack principle.
Compute sum of subarray minimums only, applying the stack-based state tracking in reverse.
Find the maximum subarray range instead of the sum, which requires similar min/max tracking but selects the largest difference.

FAQ

What is the main strategy for Sum of Subarray Ranges?

The key is using monotonic stacks to find previous and next smaller and greater elements, then aggregating each element's contribution to all subarray ranges.

Can this solution handle arrays with duplicate elements?

Yes, properly designed monotonic stacks account for duplicates when computing previous/next smaller and greater indices.

Why avoid nested loops for this problem?

Nested loops lead to O(n^2) complexity, which is inefficient for arrays up to length 1000, while monotonic stacks achieve O(n).

Is there a space-efficient version?

Monotonic stacks require O(n) space, which is optimal for tracking all previous and next min/max elements simultaneously.

How does stack-based state management help in subarray range problems?

It allows efficient determination of subarray boundaries for each element's max/min contribution, reducing redundant comparisons and achieving linear time calculation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1996 the number of weak characters in the game #1944 number of visible people in a queue #2281 sum of total strength of wizards