Sum of Subarray Ranges
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Sum of subarray ranges, Arrays, Subarray, Loops, Time Complexity, Space Complexity, Optimization, Monotonic Stack, Stack, Brute Force, brute force, subarray, preprocessing, range queries, monotonic stack, Range (Max-Min), Largest Rectangle in Histogram.
Sum of Subarray Ranges You are given an integer array nums. The range of a subarray 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 Specification The input consists of a single line containing space separated integers representing the array nums. Output Specification The output should be a single integer representing the sum of all subarray ranges. Constraints 1 <= nums.length <= 10^3 0 <= nums[i] <= 10^9 Sample Test Cases Sample Input 1: Sample Output 1: Explanation: The subarrays and their ranges are: [1]: range = 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 Sum of ranges = 0 + 0 + 0 + 1 + 1 + 2 = 4 Sample Input 2: Sample Output 2: Explanation: The subarrays and their ranges are: [1]: range = 1 1 = 0 [3]: range = 3 3 = 0 [2]: range = 2 2 = 0 [1,3]: range = 3 1 = 2 [3,2]: range = 3 2 = 1 [1,3,2]: range = 3 1 = 2 Sum of ranges = 0 + 0 + 0 + 2 + 1 + 2 = 5. Oh, wait, the sample is 3. What went wrong? Ah, range is max min. So for [1,3,2], max=3, min=1, range = 2. This seems correct. Let me recheck calculation for sample 2. [1] 0 [3] 0 [2] 0 [1,3] 3 1 = 2 [3,2] 3 2 = 1 [1,3,2] 3 1 = 2 Sum = 0+0+0+2+1+2 = 5. The sample output given is 3. This indicates a misunderstanding or a different problem. Let me re read