Sum of Subarray Ranges - Practice Coding Problems

Sum of Subarray Ranges - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3]

› Output: 4

💡 Note: Subarrays: [1] (range=0), [2] (range=0), [3] (range=0), [1,2] (range=1), [2,3] (range=1), [1,2,3] (range=2). Sum = 0+0+0+1+1+2 = 4

Example 2 — Same Elements

$ Input: nums = [1,3,3]

› Output: 4

💡 Note: Subarrays: [1] (range=0), [3] (range=0), [3] (range=0), [1,3] (range=2), [3,3] (range=0), [1,3,3] (range=2). Sum = 0+0+0+2+0+2 = 4

Example 3 — Single Element

$ Input: nums = [4]

› Output: 0

💡 Note: Only one subarray [4] with range = 4-4 = 0

Constraints

1 ≤ nums.length ≤ 1000
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,2,3]

Generate Subarrays

Find all contiguous subarrays and their ranges

Sum Ranges

Add up all the ranges: 0+1+2+0+1+0 = 4

Key Takeaway

🎯 Key Insight: Each element's contribution depends on how many subarrays it appears in as maximum vs minimum

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to calculate how much each element contributes as maximum minus how much it contributes as minimum across all subarrays. The optimal approach uses monotonic stacks to efficiently determine the range where each element is the maximum or minimum. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Optimal Solution	O(n)	O(n)	Use monotonic stacks to efficiently calculate each element's contribution
Optimized Brute Force - Track Min/Max	O(n²)	O(1)	Avoid recalculating min/max by tracking them as we extend subarrays
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and calculate their ranges

Monotonic Stack - Optimal Solution — Algorithm Steps

Use monotonic decreasing stack to find where each element is maximum
Use monotonic increasing stack to find where each element is minimum
Calculate contribution of each element
Sum all contributions

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Max Range

Use decreasing stack to find where each element is maximum

Find Min Range

Use increasing stack to find where each element is minimum

Calculate

Sum of max contributions minus sum of min contributions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int numsSize) {
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int top = -1;
    long long maxSum = 0;
    
    // Calculate sum of maximums
    for (int i = 0; i <= numsSize; i++) {
        while (top >= 0 && (i == numsSize || nums[stack[top]] <= nums[i])) {
            int mid = stack[top--];
            int left = top >= 0 ? stack[top] : -1;
            int right = i;
            maxSum += (long long)nums[mid] * (mid - left) * (right - mid);
        }
        if (i < numsSize) {
            stack[++top] = i;
        }
    }
    
    // Calculate sum of minimums
    top = -1;
    long long minSum = 0;
    
    for (int i = 0; i <= numsSize; i++) {
        while (top >= 0 && (i == numsSize || nums[stack[top]] >= nums[i])) {
            int mid = stack[top--];
            int left = top >= 0 ? stack[top] : -1;
            int right = i;
            minSum += (long long)nums[mid] * (mid - left) * (right - mid);
        }
        if (i < numsSize) {
            stack[++top] = i;
        }
    }
    
    free(stack);
    return maxSum - minSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n elements in worst case

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler