What is the brute force approach and complexity for Sum of Subarray Ranges?

Fix the start, extend the end, add (running max − running min) with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Sum of Subarray Ranges?

Two monotonic stack passes: each element times the number of subarrays it is the max (or min) of with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Sum of Subarray Ranges?

Look for key signals in the prompt: "sum over all subarrays" indicates Too many subarrays to visit → count each element's share instead.; "largest minus smallest" indicates The sum splits into Σ max − Σ min: two contribution sums.; "values up to 10^9" indicates One range is up to 2·10^9 and the totals are far bigger → long long everywhere..

Sum of Subarray Ranges

Medium·LeetCode #2104 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an integer array nums. The range of a subarray is its largest element minus its smallest element.

Return the sum of the ranges of all contiguous subarrays of nums.

Input

An integer array nums.

Output

One 64-bit integer: the sum of (max − min) over every subarray.

Example 1

Input: nums = [1, 2, 3]

Output: 4

Ranges: [1]=0, [2]=0, [3]=0, [1,2]=1, [2,3]=1, [1,2,3]=2. Total 4.

Example 2

Input: nums = [1, 3, 3]

Output: 4

Ranges: [1]=0, [3]=0, [3]=0, [1,3]=2, [3,3]=0, [1,3,3]=2. Total 4.

Example 3

Input: nums = [4, -2, -3, 4, 1]

Output: 59

Adding (max − min) over all 15 subarrays gives 59.

Constraints

• 1 ≤ nums.length ≤ 1000
• −10^9 ≤ nums[i] ≤ 10^9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sum over all subarrays”

→ Too many subarrays to visit → count each element's share instead.

“largest minus smallest”

→ The sum splits into Σ max − Σ min: two contribution sums.

“values up to 10^9”

→ One range is up to 2·10^9 and the totals are far bigger → long long everywhere.

Approach Complexity Ladder

Brute Force — every subarray with a running min and maxO(N²)O(1)

Fix the start, extend the end, add (running max − running min)

Optimal — Σ max − Σ min by contributionO(N)O(N)

Two monotonic stack passes: each element times the number of subarrays it is the max (or min) of

Brute Force Intuition

Fix the start. Move the end right one step at a time, updating the running min and max. Each step is one subarray, so add max − min to the total.

Recognition rule for this sub-pattern:

For each element, find how far it stretches left and right as the min (or max). Histograms: area = height × width. Sums over subarrays: value × (left span) × (right span), with one side strict and the other ≤ so ties count once.

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Sum of Subarray Minimums Maximal Rectangle