From Brute Force to Optimal: Subarray Ranges Explained via Monotonic Stacks 🔥

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.

Example 1:

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:

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:

Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.

Situation:

1. You are given an integer array nums
2. The range of the subarray of nums is the difference between largest and the smallest element in the sub array.

Task:

1. return the sum of all sub array ranges of nums.

Action:

1. we need to find all sub array
2. then we need to sum up all the differnce between largest and the smallest element in the sub array

🛠️ Brute Force Approach:

• Generate all subarrays
• For each, find max and min
• Time: O(n²) or worse
• ✅ Works for small inputs
• ❌ Not scalable

const subarrays = []

for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
        subarrays.push(nums.slice(i, j + 1))
    }
}

let sum = 0
for (let subarray of subarrays) {
    let min = Math.min(...subarray)
    let max = Math.max(...subarray)
    sum += max - min
}
return sum

⚡ Optimization Insight

Each number contributes to the result in 2 ways:

• As maximum in some subarrays → adds to result
• As minimum in some subarrays → subtracts from result

We count how many times it acts as max/min.

Optimized Solution O(n) Using Monotonic Stacks:

Instead of computing the range (max - min) for each subarray, flip the approach:

• For each element, how many subarrays is it the minimum in?
• For each element, how many subarrays is it the maximum in?

Use these to compute total contribution of each element to the final sum. Each element contributes to the total as:

• Maximum in some subarrays → adds value
• Minimum in some subarrays → subtracts value

We can use monotonic stack

so what are we storing? increasing or decreasing monotonic stack?

1. increasing is use to find the next smallest
2. decreasing is used to find the next greatest element in the nums
3. we are utlizing both increasing and decreasing monotonic stack

let n = nums.length
let stack = []
let prev = new Array(n).fill(-1)
let next = new Array(n).fill(n)

for (let i = 0; i < n; i++) {

decreasing monotonic stack

calculate previous smaller element, so we need increasing monotonic stack

1 2 3 4 , current nums[i] = 3

1. For next smaller elements

while (0 < stack.length 
&& nums[i] <= nums[stack[stack.length - 1]]) {
        stack.pop()
    }
    prev[i] = stack.length === 0 ? -1 : stack[stack.length - 1]
    stack.push(i)
}

 stack.length = 0

increasing monotonic stack, where the current value i. 5 if smaller on the top then pop it 1 2 3

2. For prev smaller elements

for (let i = n - 1; -1 < i; i--) {
 while (0 < stack.length 
&& nums[i] < nums[stack[stack.length - 1]]) {
        stack.pop()
    }
    next[i] = stack.length === 0 ? n : stack[stack.length - 1]
    stack.push(i)
}

now since that i have these value in prev and next with the elements that are in decreasing order???

what to do next, calculate the min?

let minSum = 0

for(let i = 0 ; i < n; i++){
  let left = i - prev[i]
  let right = next[i] - i
  minSum += nums[i] * left * right
}

3. Now finding the maxSum

stack.length = 0
prev = new Array(n).fill(-1)
next = new Array(n).fill(n)

4. For next greater elements

for (let i = 0; i < n; i++) {
 while (0 < stack.length 
  && nums[stack[stack.length - 1]] <= nums[i]) {
        stack.pop()
    }
  prev[i] = stack.length === 0 ? -1 : stack[stack.length - 1]
  stack.push(i)
}

5. For prev greater elements

stack.length = 0

for (let i = n - 1; -1 < i; i--) {
  while (0 < stack.length 
  && nums[stack[stack.length - 1]] < nums[i]) {
        stack.pop()
   }
   next[i] = stack.length === 0 ? n : stack[stack.length - 1]
   stack.push(i)
}

let maxSum = 0

for (let i = 0; i < n; i++) {
    let left = i - prev[i]
    let right = next[i] - i
    maxSum += nums[i] * left * right
}

return maxSum - minSum

🔚 Conclusion:

Instead of brute-forcing all subarrays, we flipped the problem:

How often does each element act as a min or a max?

Using monotonic stacks, we tracked that efficiently and summed their contributions.

🧠 Master this pattern and you'll unlock a whole new level in:

• Range problems
• Stack-based optimisations
• Sliding window tricks

Next time you're stuck with O(n²), think: ➡️ "Can I reframe it in terms of element contribution?