What is the time complexity of Sum of Subarray Ranges?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Sum of Subarray Ranges?

This problem uses Array, Stack, Monotonic Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Sum of Subarray Ranges?

Insight 1: Calculating the range of each subarray individually by iterating through all possible subarrays would result in O(n^2) subarrays, and finding the max and min of each would be O(n) for a total of O(n^3) complexity, which is not efficient enough. Insight 2: Instead of iterating through all subarrays directly, we can iterate through each number in the array and calculate how many subarrays this number is the maximum or minimum element in. Then calculate the total max sum and total min sum separately and subtract to find the result.

Which companies ask LeetCode 2104. Sum of Subarray Ranges in interviews?

This problem is frequently asked at J.P. Morgan, TikTok.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sum of Subarray Ranges - LeetCode 2104 Solution

Sum of Subarray Ranges - Complete Solution Guide

Sum of Subarray Ranges is LeetCode problem 2104, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to calculate the sum of ranges of all possible non-empty subarrays of a given integer array `nums`. The range of a subarray is defined as the difference between its largest and smallest elements. For example, if `nums = [1, 2, 3]`, we need to consider all subarrays: `[1]`, `[2]`, `[3]`, `[1, 2]`, `[2, 3]`, and `[1, 2, 3]`. Then, for each subarray, calculate its range (max - min) and sum up all those ranges to get the final result.

Solution Approach

The solution employs a monotonic stack approach to efficiently calculate the sum of maximums and sum of minimums of all subarrays. It first calculates the contribution of each element as the maximum element in various subarrays and sums them up. Then, it does the same for the minimum element. Finally, it subtracts the total sum of minimums from the total sum of maximums to get the final answer.

Step-by-Step Algorithm

Step 1: **Find Next Greater Element (NG) and Previous Greater or Equal Element (PGE):** For each element `nums[i]`, find the index of the next greater element to its right (NG[i]) and the index of the previous greater or equal element to its left (PGE[i]). This is done using a monotonic decreasing stack.
Step 2: **Calculate Sum of Maximums:** Iterate through the array. For each element `nums[i]`, calculate the number of subarrays where it's the maximum. This number is `(i - PGE[i]) * (NG[i] - i)`. Multiply this by `nums[i]` and add it to `sum_max`.
Step 3: **Find Next Less Element (NL) and Previous Less or Equal Element (PLE):** Similar to Step 1, find the index of the next less element to the right (NL[i]) and the index of the previous less or equal element to the left (PLE[i]). This is done using a monotonic increasing stack.
Step 4: **Calculate Sum of Minimums:** Iterate through the array. For each element `nums[i]`, calculate the number of subarrays where it's the minimum. This number is `(i - PLE[i]) * (NL[i] - i)`. Multiply this by `nums[i]` and add it to `sum_min`.
Step 5: **Calculate the Result:** Return `sum_max - sum_min`.

Key Insights

Insight 1: Calculating the range of each subarray individually by iterating through all possible subarrays would result in O(n^2) subarrays, and finding the max and min of each would be O(n) for a total of O(n^3) complexity, which is not efficient enough.
Insight 2: Instead of iterating through all subarrays directly, we can iterate through each number in the array and calculate how many subarrays this number is the maximum or minimum element in. Then calculate the total max sum and total min sum separately and subtract to find the result.
Insight 3: Monotonic stacks are the perfect data structure for finding the next greater/less and previous greater/less elements efficiently, which are used to determine the number of subarrays where each element is the maximum or minimum.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Stack, Monotonic Stack.

Companies

Asked at: J.P. Morgan, TikTok.

Sum of Subarray Ranges | LeetCode 2104

Medium

Array Stack Monotonic Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Stack;

class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;

        // Calculate sum of maximums for all subarrays
        long sum_max = 0;

        // pge: previous greater or equal
        int[] pge = new int[n];
        for (int i = 0; i < n; i++) {
            pge[i] = -1;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                pge[i] = stack.peek();
            }
            stack.push(i);
        }

        // ng: next greater
        int[] ng = new int[n];
        for (int i = 0; i < n; i++) {
            ng[i] = n;
        }
        stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                ng[stack.pop()] = i;
            }
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            sum_max += (long)nums[i] * (i - pge[i]) * (ng[i] - i);
        }

        // Calculate sum of minimums for all subarrays
        long sum_min = 0;

        // ple: previous less or equal
        int[] ple = new int[n];
        for (int i = 0; i < n; i++) {
            ple[i] = -1;
        }
        stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                ple[i] = stack.peek();
            }
            stack.push(i);
        }

        // nl: next less
        int[] nl = new int[n];
        for (int i = 0; i < n; i++) {
            nl[i] = n;
        }
        stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                nl[stack.pop()] = i;
            }
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            sum_min += (long)nums[i] * (i - ple[i]) * (nl[i] - i);
        }

        return sum_max - sum_min;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2104: Sum of Subarray Ranges - Detailed explanation and solution approaches.

Topics

Array Stack Monotonic Stack

Companies

J.P. MorganTikTok

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:2104

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: **Find Next Greater Element (NG) and Previous Greater or Equal Element (PGE):** For each element `nums[i]`, find the index of the next greater element to its right (NG[i]) and the index of the previous greater or equal element to its left (PGE[i]). This is done using a monotonic decreasing stack.
2
Step 2: **Calculate Sum of Maximums:** Iterate through the array. For each element `nums[i]`, calculate the number of subarrays where it's the maximum. This number is `(i - PGE[i]) * (NG[i] - i)`. Multiply this by `nums[i]` and add it to `sum_max`.
3
Step 3: **Find Next Less Element (NL) and Previous Less or Equal Element (PLE):** Similar to Step 1, find the index of the next less element to the right (NL[i]) and the index of the previous less or equal element to the left (PLE[i]). This is done using a monotonic increasing stack.
4
Step 4: **Calculate Sum of Minimums:** Iterate through the array. For each element `nums[i]`, calculate the number of subarrays where it's the minimum. This number is `(i - PLE[i]) * (NL[i] - i)`. Multiply this by `nums[i]` and add it to `sum_min`.
5
Step 5: **Calculate the Result:** Return `sum_max - sum_min`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

Each element in `nums` is pushed onto and popped off of the stack at most once in each of the four loops (for PGE, NG, PLE, and NL). Therefore, each loop takes O(n) time. The array traversals also take O(n) time. Thus the overall time complexity is O(n). We use four arrays of size n: pge, ng, ple, and nl along with the stack to hold the indices. Thus, the space complexity is O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays, calculate the range (max - min) for each, and sum the ranges. This is a straightforward but inefficient approach.

Time: O(n^3)Space: O(1)

Trade-offs: Simple to understand but very slow for larger arrays. Should not be used for the given constraints.

✨

Key Insights

1Insight 1: Calculating the range of each subarray individually by iterating through all possible subarrays would result in O(n^2) subarrays, and finding the max and min of each would be O(n) for a total of O(n^3) complexity, which is not efficient enough.
2Insight 2: Instead of iterating through all subarrays directly, we can iterate through each number in the array and calculate how many subarrays this number is the maximum or minimum element in. Then calculate the total max sum and total min sum separately and subtract to find the result.
3Insight 3: Monotonic stacks are the perfect data structure for finding the next greater/less and previous greater/less elements efficiently, which are used to determine the number of subarrays where each element is the maximum or minimum.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: **Duplicate Numbers:** When the array contains duplicate numbers, the 'equal' condition in 'greater or equal' and 'less or equal' is crucial to correctly count the subarrays. The problem statement does not explicitly state how to handle duplicates. The provided code treats numbers as 'equal' when searching for previous/next less/greater elements, which is essential to find the count correctly.
Edge case 2: **Single Element Array:** If the array has only one element, the range is 0, and the algorithm should return 0. This is handled correctly because pge and ple will be -1, and ng and nl will be n, leading to (i - pge[i]) * (ng[i] - i) = (0 - (-1)) * (1 - 0) = 1 for sum_max and similarly for sum_min, canceling out and returning 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: **Incorrect Stack Logic:** The monotonic stack must maintain either increasing or decreasing order. Forgetting to pop elements that violate the order will lead to incorrect results.

✗Common mistake 2: **Integer Overflow:** When calculating `sum_max` and `sum_min`, the intermediate results can be large, potentially leading to integer overflow. Using `long long` (or `long` in Java) is necessary to prevent this.

✗Common mistake 3: Forgetting to handle the 'equal' condition in monotonic stacks when finding previous/next less/greater elements, particularly when the input contains duplicate values.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: **Stock Span Problem:** This problem is related to the stock span problem, where we need to find the number of consecutive days before a given day when the stock price was less than or equal to the price on the given day. The monotonic stack technique is used to solve both efficiently.

🏦Real-world scenario 2: **Finding local maxima/minima:** In signal processing, finding local maxima and minima is important. Monotonic stacks can be used to find these efficiently in a stream of data.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Sum of Subarray Ranges"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?