We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Subarray Ranges

Difficulty: Medium

Problem Description

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.

Key Insights

  • The range of a subarray is calculated as the difference between its maximum and minimum values.
  • Each element in the array can serve as both a maximum and a minimum in various subarrays.
  • We can efficiently calculate the contribution of each element to the total sum of ranges using a monotonic stack to determine how many subarrays an element is the maximum or minimum for.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a monotonic stack approach. We will calculate the contribution of each element being the maximum and the minimum for all the subarrays in which it appears.

  1. Calculate Contributions:

    • For each element, determine how many subarrays it is the maximum for and how many it is the minimum for using two monotonic stacks.
    • For maximums, we push elements onto the stack, and whenever a larger element is encountered, we pop from the stack, calculating the contribution of the popped element based on its position.
    • Repeat similarly for minimums.

  2. Final Calculation:

    • The total sum of all subarray ranges can be computed by subtracting the total contributions of minimums from the total contributions of maximums.

This algorithm ensures we find the contributions in linear time.

Code Solutions

def sum_of_subarray_ranges(nums):
    n = len(nums)
    
    # Initialize variables for the total sum
    total_max_contribution = 0
    total_min_contribution = 0
    
    # Calculate contribution when nums[i] is the maximum
    max_stack = []
    for i in range(n):
        while max_stack and nums[max_stack[-1]] < nums[i]:
            j = max_stack.pop()
            left = max_stack[-1] if max_stack else -1
            total_max_contribution += nums[j] * (i - j) * (j - left)
        max_stack.append(i)
    
    while max_stack:
        j = max_stack.pop()
        left = max_stack[-1] if max_stack else -1
        total_max_contribution += nums[j] * (n - j) * (j - left)
    
    # Calculate contribution when nums[i] is the minimum
    min_stack = []
    for i in range(n):
        while min_stack and nums[min_stack[-1]] > nums[i]:
            j = min_stack.pop()
            left = min_stack[-1] if min_stack else -1
            total_min_contribution += nums[j] * (i - j) * (j - left)
        min_stack.append(i)
    
    while min_stack:
        j = min_stack.pop()
        left = min_stack[-1] if min_stack else -1
        total_min_contribution += nums[j] * (n - j) * (j - left)
    
    # The final result is the difference between max and min contributions
    return total_max_contribution - total_min_contribution
← Back to All Questions