Sum of Subarray Ranges solution and explanation
Google
9 more videos on this problem
L10. Sum of subarray ranges | Stack and Queue Playlisttake U forward · 10:34 · 165K views
LeetCode 2104 - Sum of Subarray Ranges - Brute ForceSandeep Kumar · 8:13 · 18K views
2104. Sum of Subarray Ranges (Leetcode Medium)Programming Live with Larry · 6:33 · 14K views
Sum of Subarray Ranges | Leetcode | Medium | Java | Striver's A to Z DSA Course/SheetAlgorithmHQ · 12:19 · 11K views
LeetCode 2104. Sum of Subarray RangesKacy Codes · 24:37 · 10K views
[ LeetCode 2104 ] Sum of Subarray Ranges | Monotonic StackLulu Code · 18:57 · 8K views
2104. Sum of Subarray Ranges (LeetCode)hakunamatasq · 3:18 · 2K views
Stack - 17 | 2104. Sum of Subarray RangesCTO Bhaiya · 23:53 · 1K views
2104 Sum of Subarray Ranges(Python & Stack & full walk thru)AlgBreaker · 29:34 · 646 views
[ LeetCode 2104 ] Sum of Subarray Ranges | Coding | PythonLulu Code · 6:54 · 639 views
The problem
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.
Constraints:
1 <= nums.length <= 1000-109 <= nums[i] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
Approach overview
Problem Overview: You are given an integer array and must compute the sum of ranges for all subarrays. The range of a subarray equals max(subarray) - min(subarray). The task is to efficiently aggregate this value across every possible subarray.
Approach 1: Brute Force Expansion (O(n²) time, O(1) space)
Start a subarray at each index and expand it to the right. While expanding, maintain the current minimum and maximum values. Each time the window grows, update min and max, then add max - min to the result. This avoids recomputing min and max from scratch but still requires checking every subarray pair (i, j). The algorithm runs in O(n²) time with constant extra space. This approach is straightforward and useful for validating logic, but it becomes slow for large arrays because the number of subarrays grows quadratically.
Approach 2: Monotonic Stack Contribution Method (O(n) time, O(n) space)
The key observation is that each element contributes to multiple subarrays as both a maximum and a minimum. Instead of enumerating subarrays, count how many subarrays treat a value as their maximum and how many treat it as their minimum. The difference between these contributions determines its impact on the final sum.
Use monotonic stacks to find the previous and next greater elements for maximum contribution and the previous and next smaller elements for minimum contribution. For an index i, the number of subarrays where nums[i] is the maximum equals (i - prevGreater) * (nextGreater - i). Apply a similar calculation using smaller elements to count when it acts as the minimum. Multiply each count by the element value and accumulate the difference.
This transforms the problem into two linear scans using stack operations such as push, pop, and index tracking. Each element enters and leaves the stack once, producing O(n) time complexity and O(n) auxiliary space. The technique is widely used in problems involving subarray contributions and boundary discovery in stack-based algorithms on an array.
Recommended for interviews: Interviewers expect the monotonic stack solution because it demonstrates understanding of contribution counting and boundary discovery. Implementing the brute force approach first shows problem comprehension, but the O(n) stack solution shows strong algorithmic intuition and familiarity with advanced array techniques.
Approach 1: Brute Force Approach
The Brute Force Approach involves iterating over all possible subarrays of the given array. For each subarray, find the maximum and minimum elements, and calculate the difference. Sum all these differences to get the final answer. While this approach is simple, it is not efficient for larger arrays due to its quadratic time complexity.
def subArrayRanges(nums):
total = 0
n = len(nums)
for i in range(n):
min_val = float('inf')
max_val = float('-inf')
for j in range(i, n):
max_val = max(max_val, nums[j])
min_val = min(min_val, nums[j])
total += max_val - min_val
return total
# Example Usage
print(subArrayRanges([1, 2, 3]))import java.util.*;
public class SubarrayRanges {
public static int subArrayRanges(int[] nums) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
for (int j = i; j < n; j++) {
maxVal = Math.max(maxVal, nums[j]);
minVal = Math.min(minVal, nums[j]);
sum += (maxVal - minVal);
}
}
return sum;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
System.out.println(subArrayRanges(nums));
}
}#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int subArrayRanges(vector<int>& nums) {
int sum = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
int minVal = INT_MAX;
int maxVal = INT_MIN;
for (int j = i; j < n; j++) {
maxVal = max(maxVal, nums[j]);
minVal = min(minVal, nums[j]);
sum += (maxVal - minVal);
}
}
return sum;
}
int main() {
vector<int> nums = {1, 2, 3};
cout << subArrayRanges(nums) << endl;
return 0;
}function subArrayRanges(nums) {
let sum = 0;
const n = nums.length;
for (let i = 0; i < n; i++) {
let minVal = Infinity;
let maxVal = -Infinity;
for (let j = i; j < n; j++) {
maxVal = Math.max(maxVal, nums[j]);
minVal = Math.min(minVal, nums[j]);
sum += maxVal - minVal;
}
}
return sum;
}
console.log(subArrayRanges([1, 2, 3]));#include <stdio.h>
#include <limits.h>
int subArrayRanges(int* nums, int numsSize){
int sum = 0;
for (int i = 0; i < numsSize; i++) {
int minVal = INT_MAX;
int maxVal = INT_MIN;
for (int j = i; j < numsSize; j++) {
if (nums[j] > maxVal) maxVal = nums[j];
if (nums[j] < minVal) minVal = nums[j];
sum += (maxVal - minVal);
}
}
return sum;
}
int main() {
int nums[] = {1, 2, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", subArrayRanges(nums, numsSize));
return 0;
}using System;
public class SubarrayRanges {
public static int SubArrayRanges(int[] nums) {
int sum = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
int minVal = int.MaxValue;
int maxVal = int.MinValue;
for (int j = i; j < n; j++) {
maxVal = Math.Max(maxVal, nums[j]);
minVal = Math.Min(minVal, nums[j]);
sum += (maxVal - minVal);
}
}
return sum;
}
public static void Main() {
int[] nums = {1, 2, 3};
Console.WriteLine(SubArrayRanges(nums));
}
}Utilizes a similar double loop structure. The Python code leverages built-in functions to manage and compute maximum and minimum values within the subarrays.
Time Complexity: O(n^2), iterating over all subarrays
Space Complexity: O(1), minimal space is used beyond counter variables.
Approach 2: Monotonic Stack Approach
The Monotonic Stack Approach optimizes the calculation by focusing on the contribution of each element as a maximum or minimum in various subarrays. By using two stacks, the solution efficiently determines the range extend of each number within the subarray, deriving the number of subarrays it could be the maximum or minimum of. This optimized approach emphasizes reducing redundant calculations commonly inherent in brute force methods.
def subArrayRanges(nums):
max_sum = 0
min_sum = 0
n = len(nums)
stack = []
prev = [0] * n
next_ = [0] * n
# Calculate Next and Previous for Minimum
for i in range(n):
while stack and nums[stack[-1]] > nums[i]:
next_[stack.pop()] = i
stack.append(i)
while stack:
next_[stack.pop()] = n
for i in range(n-1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
prev[stack.pop()] = i
stack.append(i)
while stack:
prev[stack.pop()] = -1
for i in range(n):
min_sum += nums[i] * (i - prev[i]) * (next_[i] - i)
# Calculate Next and Previous for Maximum
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
next_[stack.pop()] = i
stack.append(i)
while stack:
next_[stack.pop()] = n
for i in range(n-1, -1, -1):
while stack and nums[stack[-1]] <= nums[i]:
prev[stack.pop()] = i
stack.append(i)
while stack:
prev[stack.pop()] = -1
for i in range(n):
max_sum += nums[i] * (i - prev[i]) * (next_[i] - i)
return max_sum - min_sum
# Example Usage
print(subArrayRanges([1, 2, 3]))import java.util.*;
public class SubarrayRanges {
public static int subArrayRanges(int[] nums) {
long maxSum = 0, minSum = 0;
int n = nums.length;
int[] prev = new int[n], next = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
next[stack.pop()] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) next[stack.pop()] = n;
for (int i = n - 1; i >= 0; --i) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
prev[stack.pop()] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) prev[stack.pop()] = -1;
for (int i = 0; i < n; i++) {
minSum += (long)(i - prev[i]) * (next[i] - i) * nums[i];
}
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
next[stack.pop()] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) next[stack.pop()] = n;
for (int i = n - 1; i >= 0; --i) {
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
prev[stack.pop()] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) prev[stack.pop()] = -1;
for (int i = 0; i < n; i++) {
maxSum += (long)(i - prev[i]) * (next[i] - i) * nums[i];
}
return (int)(maxSum - minSum);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
System.out.println(subArrayRanges(nums));
}
}#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int subArrayRanges(vector<int>& nums) {
long long maxSum = 0, minSum = 0;
vector<int> prev(nums.size()), next(nums.size());
stack<int> st;
for (int i = 0; i < nums.size(); ++i) {
while (!st.empty() && nums[st.top()] > nums[i]) {
next[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
next[st.top()] = nums.size();
st.pop();
}
for (int i = nums.size() - 1; i >= 0; --i) {
while (!st.empty() && nums[st.top()] >= nums[i]) {
prev[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
prev[st.top()] = -1;
st.pop();
}
for (int i = 0; i < nums.size(); i++) {
minSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
}
for (int i = 0; i < nums.size(); ++i) {
while (!st.empty() && nums[st.top()] < nums[i]) {
next[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
next[st.top()] = nums.size();
st.pop();
}
for (int i = nums.size() - 1; i >= 0; --i) {
while (!st.empty() && nums[st.top()] <= nums[i]) {
prev[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
prev[st.top()] = -1;
st.pop();
}
for (int i = 0; i < nums.size(); i++) {
maxSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
}
return (int)(maxSum - minSum);
}
int main() {
vector<int> nums = {1, 2, 3};
cout << subArrayRanges(nums) << endl;
return 0;
}function subArrayRanges(nums) {
let maxSum = 0, minSum = 0;
const n = nums.length;
const prev = new Array(n).fill(0);
const next = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; ++i) {
while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
next[stack.pop()] = i;
}
stack.push(i);
}
while (stack.length) next[stack.pop()] = n;
for (let i = n - 1; i >= 0; --i) {
while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
prev[stack.pop()] = i;
}
stack.push(i);
}
while (stack.length) prev[stack.pop()] = -1;
for (let i = 0; i < n; i++) {
minSum += (i - prev[i]) * (next[i] - i) * nums[i];
}
for (let i = 0; i < n; ++i) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
next[stack.pop()] = i;
}
stack.push(i);
}
while (stack.length) next[stack.pop()] = n;
for (let i = n - 1; i >= 0; --i) {
while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
prev[stack.pop()] = i;
}
stack.push(i);
}
while (stack.length) prev[stack.pop()] = -1;
for (let i = 0; i < n; i++) {
maxSum += (i - prev[i]) * (next[i] - i) * nums[i];
}
return maxSum - minSum;
}
console.log(subArrayRanges([1, 2, 3]));#include <stdio.h>
#include <stdlib.h>
int subArrayRanges(int* nums, int numsSize) {
long long maxSum = 0, minSum = 0;
int* prev = (int*)malloc(sizeof(int) * numsSize);
int* next = (int*)malloc(sizeof(int) * numsSize);
// Calculate the minimums in subarrays
for (int i = 0; i < numsSize; i++) {
while (stackSize > 0 && nums[stack[stackSize - 1]] > nums[i]) {
next[stack[--stackSize]] = i;
}
stack[stackSize++] = i;
}
while (stackSize > 0) next[stack[--stackSize]] = numsSize;
for (int i = numsSize - 1; i >= 0; i--) {
while (stackSize > 0 && nums[stack[stackSize - 1]] >= nums[i]) {
prev[stack[--stackSize]] = i;
}
stack[stackSize++] = i;
}
while (stackSize > 0) prev[stack[--stackSize]] = -1;
for (int i = 0; i < numsSize; i++) {
minSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
}
// Calculate the maximums in subarrays using similar steps
for (int i = 0; i < numsSize; i++) {
while (stackSize > 0 && nums[stack[stackSize - 1]] < nums[i]) {
next[stack[--stackSize]] = i;
}
stack[stackSize++] = i;
}
while (stackSize > 0) next[stack[--stackSize]] = numsSize;
for (int i = numsSize - 1; i >= 0; i--) {
while (stackSize > 0 && nums[stack[stackSize - 1]] <= nums[i]) {
prev[stack[--stackSize]] = i;
}
stack[stackSize++] = i;
}
while (stackSize > 0) prev[stack[--stackSize]] = -1;
for (int i = 0; i < numsSize; i++) {
maxSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
}
free(prev);
free(next);
free(stack);
return (int)(maxSum - minSum);
}
int main() {
int nums[] = {1, 2, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", subArrayRanges(nums, numsSize));
return 0;
}using System;
using System.Collections.Generic;
public class SubarrayRanges {
public static int SubArrayRanges(int[] nums) {
long maxSum = 0, minSum = 0;
int n = nums.Length;
int[] prev = new int[n], next = new int[n];
Stack<int> stack = new Stack<int>();
for (int i = 0; i < n; ++i) {
while (stack.Count > 0 && nums[stack.Peek()] > nums[i]) {
next[stack.Pop()] = i;
}
stack.Push(i);
}
while (stack.Count > 0) next[stack.Pop()] = n;
for (int i = n - 1; i >= 0; --i) {
while (stack.Count > 0 && nums[stack.Peek()] >= nums[i]) {
prev[stack.Pop()] = i;
}
stack.Push(i);
}
while (stack.Count > 0) prev[stack.Pop()] = -1;
for (int i = 0; i < n; i++) {
minSum += (long)(i - prev[i]) * (next[i] - i) * nums[i];
}
for (int i = 0; i < n; ++i) {
while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
next[stack.Pop()] = i;
}
stack.Push(i);
}
while (stack.Count > 0) next[stack.Pop()] = n;
for (int i = n - 1; i >= 0; --i) {
while (stack.Count > 0 && nums[stack.Peek()] <= nums[i]) {
prev[stack.Pop()] = i;
}
stack.Push(i);
}
while (stack.Count > 0) prev[stack.Pop()] = -1;
for (int i = 0; i < n; i++) {
maxSum += (long)(i - prev[i]) * (next[i] - i) * nums[i];
}
return (int)(maxSum - minSum);
}
public static void Main() {
int[] nums = {1, 2, 3};
Console.WriteLine(SubArrayRanges(nums));
}
}The Python implementation operates through utilization of stacks for detecting array element subarray contribution over its capability of being minimally or maximally relevant over calculated ranges.
Time Complexity: O(n), principally due to optimized stack implementations tightly controlling the number of operative passes.
Space Complexity: O(n), incurring stack space redundancy, albeit efficiently controlled through methodology.
Approach 3: Default Approach
function subArrayRanges(nums: number[]): number {
const n = nums.length;
let res = 0;
for (let i = 0; i < n - 1; i++) {
let min = nums[i];
let max = nums[i];
for (let j = i + 1; j < n; j++) {
min = Math.min(min, nums[j]);
max = Math.max(max, nums[j]);
res += max - min;
}
}
return res;
}func subArrayRanges(nums []int) int64 {
var ans int64
n := len(nums)
for i := 0; i < n-1; i++ {
mi, mx := nums[i], nums[i]
for j := i + 1; j < n; j++ {
mi = min(mi, nums[j])
mx = max(mx, nums[j])
ans += (int64)(mx - mi)
}
}
return ans
}impl Solution {
pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut res: i64 = 0;
for i in 1..n {
let mut min = nums[i - 1];
let mut max = nums[i - 1];
for j in i..n {
min = min.min(nums[j]);
max = max.max(nums[j]);
res += (max - min) as i64;
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), iterating over all subarrays |
| Monotonic Stack Approach | Time Complexity: O(n), principally due to optimized stack implementations tightly controlling the number of operative passes. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(n²) | O(1) | Useful for understanding the problem or verifying correctness on small arrays |
| Monotonic Stack Contribution | O(n) | O(n) | Best choice for large inputs and expected solution in coding interviews |
Frequently asked questions
Is Sum of Subarray Ranges easy or hard?
The problem is rated Medium on LeetCode. Understanding the brute force solution is straightforward, but deriving the O(n) monotonic stack approach requires familiarity with subarray contribution techniques and boundary discovery.
How to solve Sum of Subarray Ranges in O(n)?
Compute the contribution of each element as both a maximum and a minimum. Use monotonic stacks to find the previous and next greater elements for maximum contribution and previous and next smaller elements for minimum contribution. Multiply the distances to count how many subarrays include that element as the boundary.
What is the best approach for Sum of Subarray Ranges?
The optimal solution uses a monotonic stack to compute how many subarrays treat each element as a maximum and as a minimum. By calculating these contributions separately and subtracting them, the total range sum can be derived in O(n) time. This avoids enumerating every subarray.
Is Sum of Subarray Ranges asked at Google/Amazon/Meta?
Sum of Subarray Ranges represents a common interview pattern involving monotonic stacks and subarray contribution counting. Variants of this pattern frequently appear in interviews at companies like Amazon, Google, and Meta because they test deeper understanding of array boundaries and stack techniques.
What data structure is used in Sum of Subarray Ranges?
The optimal solution uses a monotonic stack. The stack maintains indices in increasing or decreasing order to efficiently find previous and next greater or smaller elements in linear time.
What is the time complexity of Sum of Subarray Ranges?
The brute force method runs in O(n^2) time because it checks every subarray while tracking the current minimum and maximum. The optimal monotonic stack approach runs in O(n) time since each element is pushed and popped from the stack at most once.
Sum of Subarray Ranges Python or Java solution approach
Python and Java implementations typically follow the same pattern: compute contributions for maximum values using a decreasing monotonic stack, then compute contributions for minimum values using an increasing stack. Both passes run in O(n) time and store indices in the stack.