Problem Description

You are given an integer array nums. For each subarray in nums, you need to find its range, which is defined as the difference between the maximum element and minimum element in that subarray.

Your task is to calculate the sum of ranges of all possible subarrays and return this total sum.

A subarray is a contiguous sequence of one or more elements from the original array. For example, if nums = [1, 2, 3], the subarrays are: [1], [2], [3], [1,2], [2,3], and [1,2,3].

For each subarray:

• Find the maximum element
• Find the minimum element
• Calculate the range as max - min
• Add this range to the running sum

The solution uses a nested loop approach where for each starting position i, it considers all subarrays starting at i and ending at positions j (where j >= i). As it extends each subarray, it tracks the running minimum and maximum values, calculates the range, and adds it to the total sum.

For example, with nums = [1, 3, 2]:

• Subarray [1]: range = 1 - 1 = 0
• Subarray [3]: range = 3 - 3 = 0
• Subarray [2]: range = 2 - 2 = 0
• Subarray [1, 3]: range = 3 - 1 = 2
• Subarray [3, 2]: range = 3 - 2 = 1
• Subarray [1, 3, 2]: range = 3 - 1 = 2
• Total sum = 0 + 0 + 0 + 2 + 1 + 2 = 5

Intuition

The key insight is that we need to examine every possible subarray and calculate its range. Since a subarray is defined by its starting and ending positions, we can systematically generate all subarrays using two pointers.

The brute force approach is actually quite natural here: for each possible starting position i, we expand the subarray by moving the ending position j from i to the end of the array. This generates all subarrays starting at position i.

The clever optimization in this solution is that we don't need to recalculate the minimum and maximum from scratch for each subarray. When we extend a subarray from [i...j-1] to [i...j], we only need to:

• Update the minimum: mi = min(mi, nums[j])
• Update the maximum: mx = max(mx, nums[j])

This works because adding one more element to a subarray can only potentially change the min/max if the new element is smaller than the current minimum or larger than the current maximum.

For example, if we have subarray [3, 1] with min=1, max=3, and we extend it to [3, 1, 5], we only need to compare 5 with our current min and max values, rather than scanning through all three elements again.

This incremental update approach reduces redundant calculations. Instead of recalculating min/max for each subarray from scratch (which would take O(n³) time), we maintain running min/max values as we expand each subarray, achieving O(n²) time complexity.

The solution iterates through all n*(n+1)/2 possible subarrays exactly once, computing each range in constant time using the maintained min/max values, and accumulating the sum of all ranges.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The implementation uses a nested loop structure to enumerate all possible subarrays and calculate their ranges efficiently.

Algorithm Steps:

1. Initialize variables: Set ans = 0 to store the sum of all ranges, and get the array length n.

2. Outer loop (i from 0 to n-2): This loop sets the starting position of each subarray. We stop at n-2 because we need at least one more element to form a subarray with the next position.

3. Initialize min/max trackers: For each starting position i, initialize both mi (minimum) and mx (maximum) to nums[i]. These will track the minimum and maximum values in the current subarray as we expand it.

4. Inner loop (j from i+1 to n-1): This loop extends the subarray from position i to position j.

   • Update the minimum: mi = min(mi, nums[j])
   • Update the maximum: mx = max(mx, nums[j])
   • Calculate the range: mx - mi
   • Add the range to the total sum: ans += mx - mi

5. Return the result: After processing all subarrays, return ans.

Key Implementation Details:

• The outer loop starts at each possible subarray starting position
• The inner loop extends the subarray one element at a time
• By maintaining running mi and mx values, we avoid recalculating the min/max for the entire subarray each time
• Note that single-element subarrays (where i == j) have a range of 0 since min equals max. The code handles this implicitly by starting the inner loop at i+1, and these single-element ranges contribute 0 to the sum

Time Complexity: O(n²) - We have two nested loops, each iterating through the array.

Space Complexity: O(1) - We only use a constant amount of extra space for variables ans, mi, and mx.

This brute force approach is straightforward and efficient enough for moderate input sizes, as it processes each subarray exactly once with minimal overhead.

Example Walkthrough

Let's walk through the solution with nums = [4, 1, 3]:

Step 1: Initialize

• ans = 0 (to accumulate the sum of ranges)
• n = 3 (length of array)

Step 2: Process subarrays starting at index 0 (i = 0)

• Initialize: mi = 4, mx = 4
• Extend to j = 1: nums[1] = 1
  • Update: mi = min(4, 1) = 1, mx = max(4, 1) = 4
  • Range of [4, 1] = 4 - 1 = 3
  • Add to sum: ans = 0 + 3 = 3
• Extend to j = 2: nums[2] = 3
  • Update: mi = min(1, 3) = 1, mx = max(4, 3) = 4
  • Range of [4, 1, 3] = 4 - 1 = 3
  • Add to sum: ans = 3 + 3 = 6

Step 3: Process subarrays starting at index 1 (i = 1)

• Initialize: mi = 1, mx = 1
• Extend to j = 2: nums[2] = 3
  • Update: mi = min(1, 3) = 1, mx = max(1, 3) = 3
  • Range of [1, 3] = 3 - 1 = 2
  • Add to sum: ans = 6 + 2 = 8

Step 4: No more starting positions (i = 2 would be the last element)

Result: Total sum = 8

Note: Single-element subarrays [4], [1], [3] each have range = 0 (max - min = 0), so they don't contribute to the sum. The algorithm implicitly handles these by starting the inner loop at i+1.

The key efficiency comes from maintaining running min/max values as we extend each subarray, rather than recalculating them from scratch each time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code uses two nested loops:

• The outer loop runs from i = 0 to i = n-2, which executes n-1 times
• For each iteration i, the inner loop runs from j = i+1 to j = n-1, which executes n-i-1 times

The total number of iterations is: (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2

Inside the inner loop, we perform constant time operations (min(), max(), and addition), each taking O(1) time.

Therefore, the overall time complexity is O(n²).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• ans: stores the running sum
• n: stores the length of the array
• i, j: loop counters
• mi, mx: track minimum and maximum values for current subarray

All these variables use O(1) space regardless of the input size, making the space complexity O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Missing Single-Element Subarrays

The Pitfall: The current implementation starts the inner loop at start_index + 1, which means it never explicitly processes single-element subarrays. While this happens to work correctly (since single-element subarrays have a range of 0 and don't contribute to the sum), it can lead to confusion and potential bugs if the problem requirements change.

Why It Happens: Developers might assume all subarrays are being processed, but the code structure skips the case where start_index == end_index.

Solution: Make the code more explicit and complete by handling all subarrays:

def subArrayRanges(self, nums: List[int]) -> int:
    total_range_sum = 0
    array_length = len(nums)
  
    # Process ALL subarrays, including single elements
    for start_index in range(array_length):
        current_min = nums[start_index]
        current_max = nums[start_index]
      
        # Start from start_index (not start_index + 1)
        for end_index in range(start_index, array_length):
            current_min = min(current_min, nums[end_index])
            current_max = max(current_max, nums[end_index])
            total_range_sum += current_max - current_min
  
    return total_range_sum

2. Integer Overflow in Other Languages

The Pitfall: When implementing this solution in languages like C++ or Java, the sum might exceed the integer limit for large arrays with large values.

Why It Happens: With n elements, there are n(n+1)/2 subarrays. If n=1000 and ranges are large, the sum can exceed 32-bit integer limits.

Solution: Use appropriate data types:

• In Python: This isn't an issue due to arbitrary precision integers
• In Java: Use long instead of int for the sum
• In C++: Use long long for the accumulator

3. Off-by-One Error in Loop Bounds

The Pitfall: Using range(array_length - 1) for the outer loop when you actually want to process all starting positions.

Why It Happens: Confusion about whether single-element subarrays should be included, or misunderstanding that the last element can also be a starting position.

Solution: Carefully consider the loop bounds:

• If including single-element subarrays: outer loop should be range(array_length)
• If excluding them (as in original): outer loop range(array_length - 1) is correct but document this choice clearly

4. Inefficient Min/Max Recalculation

The Pitfall: Some might be tempted to recalculate min and max for the entire subarray in each iteration:

# INEFFICIENT - Don't do this!
for start_index in range(array_length):
    for end_index in range(start_index, array_length):
        subarray = nums[start_index:end_index+1]
        total_range_sum += max(subarray) - min(subarray)

Why It Happens: It seems more straightforward to work with the actual subarray.

Solution: Always maintain running min/max values as shown in the original solution. This reduces time complexity from O(n³) to O(n²).