Sum of Subarray Ranges | Stack and Queue

Welcome back to the Stack and Queue Data Structures and Algorithms (DSA) playlist. This chapter covers the problem "Sum of Subarray Ranges", demonstrating how to transition from a straightforward $O(n^2)$ brute-force approach to an optimized $O(n)$ solution by breaking the problem down into two classic sub-problems: Sum of Subarray Maximums and Sum of Subarray Minimums.

1. Problem Statement: Understanding Subarray Ranges

Given an array of numbers, the task is to generate all possible subarrays, compute the range for each subarray, and return the total sum of all these ranges.

• Subarray: A contiguous part of an array.
• Subarray Range: The difference between the largest element and the smallest element in a particular subarray:

Concrete Example Walkthrough

Consider the input array: [1, 4, 3, 2]

Let's list all possible contiguous subarrays and evaluate their ranges:

Summing up all individual subarray ranges:

2. Naive Approach: The Brute-Force Solution

To solve this naively, we can generate all possible subarrays using nested loops. As we traverse each subarray from index i to j, we keep track of the running maximum and minimum elements.

Naive Implementation (Java / Pseudocode)

public long subArrayRanges(int[] nums) {
    long sum = 0;
    int n = nums.length;
    
    for (int i = 0; i < n; i++) {
        int largest = nums[i];
        int smallest = nums[i];
        
        for (int j = i + 1; j < n; j++) {
            largest = Math.max(largest, nums[j]);
            smallest = Math.min(smallest, nums[j]);
            
            // Add range of current subarray nums[i...j]
            sum += (long)(largest - smallest);
        }
    }
    return sum;
}

Complexity Analysis of Brute Force

• Time Complexity: $O(n^2)$ due to the nested loops generating every subarray.
• Space Complexity: $O(1)$ auxiliary space.

Note: An $O(n^2)$ solution is typically unacceptable in interviews for this class of array problems, especially when the interviewer expects a linear or near-linear time optimization using monotonic stacks.

3. The Core Insight: Mathematical Decomposition

When an interviewer pushes for an optimization beyond $O(n^2)$, it is a clear signal to look for a linear $O(n)$ or $O(n \log n)$ approach.

Let's expand the summation of ranges for our example array [1, 4, 3, 2]:

Using the associative and commutative properties of addition, we can rearrange the terms:

Notice what this grouping yields:

1. First Group: Sum of the largest elements across all possible subarrays.
2. Second Group: Sum of the smallest elements across all possible subarrays.

Therefore, the master equation is:

4. Leveraging Existing Building Blocks: Max and Min Subarrays

Instead of inventing a brand new complex data structure, we can reuse solutions from two prerequisite problems covered in this playlist:

1. Sum of Subarray Minimums: Computes the sum of minimum elements across all subarrays in linear time $O(n)$ using monotonic stacks.
2. Sum of Subarray Maximums: Computes the sum of maximum elements across all subarrays using an identical monotonic stack pattern (just reversing the comparison operator).

Once you know how to solve for the sum of minimums, solving for maximums is symmetric.

5. Step-by-Step Flow Walkthrough

6. Optimized Code Architecture

Here is how the clean, decoupled solution comes together by combining the two underlying helper functions:

class Solution {
    public long subArrayRanges(int[] nums) {
        return sumSubarrayMaxs(nums) - sumSubarrayMins(nums);
    }
    
    private long sumSubarrayMaxs(int[] nums) {
        // Implementation using Monotonic Decreasing Stack
        // Returns the sum of maximums for all subarrays
        // (Placeholder for standard monotonic stack logic taking ~5N operations)
        long totalMax = 0;
        // ... monotonic stack logic for maximums ...
        return totalMax;
    }
    
    private long sumSubarrayMins(int[] nums) {
        // Implementation using Monotonic Increasing Stack
        // Returns the sum of minimums for all subarrays
        // (Placeholder for standard monotonic stack logic taking ~5N operations)
        long totalMin = 0;
        // ... monotonic stack logic for minimums ...
        return totalMin;
    }
}

7. Complexity Analysis of the Optimized Solution

• Time Breakdown: Running sumSubarrayMaxs takes roughly $5n$ operations, and sumSubarrayMins takes another $5n$ operations. Combined, it takes $10n$ operations, which simplifies asymptotically to $O(n)$.
• Space Breakdown: Storing previous/next greater/smaller element index arrays or stack frames takes linear auxiliary space $O(n)$, which is vastly superior to $O(n^2)$ for large inputs.

Summary and Key Takeaways

• Problem Definition: The sum of subarray ranges is the cumulative difference between the maximum and minimum elements across every contiguous subarray.
• Brute-Force Limitation: Generating every subarray and tracking min/max iteratively results in an inefficient $O(n^2)$ time complexity.
• Mathematical Decomposition: The range sum can be decoupled into two independent components: the sum of all subarray maximums minus the sum of all subarray minimums.
• Modular Reusability: By solving Sum of Subarray Minimums using a monotonic stack, you can easily adapt the same logic (flipping comparisons) to solve Sum of Subarray Maximums.
• Linear Optimization: Combining both monotonic stack passes reduces the overall time and space complexity from quadratic $O(n^2)$ down to optimal linear $O(n)$.
• Interview Strategy: When interviewers present seemingly complex range or window queries, look for algebraic decompositions that allow you to split the problem into well-known standard patterns.