Given an integer array arr[], the range of a subarray is defined as the difference between the largest and smallest elements within that subarray. Find the sum of the ranges of all possible subarrays of the array.
Examples:
Input: arr[] = [1, 2, 3]
Output: 4
Explanation: All possible subarrays and their ranges are:
[1] → 1 - 1 = 0
[2] → 2 - 2 = 0
[3] → 3 - 3 = 0
[1, 2] → 2 - 1 = 1
[2, 3] → 3 - 2 = 1
[1, 2, 3] → 3 - 1 = 2
Sum of all ranges = 0 + 0 + 0 + 1 + 1 + 2 = 4Input: arr[] = [-32, 0, -2, 72]
Output: 318
Explanation: All possible subarrays and their ranges are:
[-32] → -32 - (-32) = 0
[-32, 0] → 0 - (-32) = 32
[-32, 0, -2] → 0 - (-32) = 32
[-32, 0, -2, 72] → 72 - (-32) = 104
[0] → 0 - 0 = 0
[0, -2] → 0 - (-2) = 2
[0, -2, 72] → 72 - (-2) = 74
[-2] → -2 - (-2) = 0
[-2, 72] → 72 - (-2) = 74
[72] → 72 - 72 = 0
Sum of all ranges = 0 + 32 + 32 + 104 + 0 + 2 + 74 + 0 + 74 + 0 = 318
Table of Content
[Naive Approach] Computing in all subarray - O(n2) Time and O(1) Space
The idea is to generate all possible subarrays of the given array using two nested loops. For each subarray, we traverse through its elements to find the minimum and maximum values. Once these are identified, we calculate the difference between them, which gives the range of that subarray. We then add up the ranges of all subarrays to get the final result.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int subarrayRanges(vector<int>& arr) {
int n = arr.size();
int totalSum = 0;
// generate all subarrays using two nested loops
for (int i = 0; i < n; i++) {
int currentMin = INT_MAX;
int currentMax = INT_MIN;
// extend subarray from index i to j
for (int j = i; j < n; j++) {
// update currentMin and currentMax
// for this subarray
currentMin = min(currentMin, arr[j]);
currentMax = max(currentMax, arr[j]);
// add range of this subarray to totalSum
totalSum += (currentMax - currentMin);
}
}
return totalSum;
}
int main() {
vector<int> arr = {1, 2, 3};
cout << subarrayRanges(arr) << endl;
return 0;
}
class GfG {
static int subarrayRanges(int[] arr) {
int n = arr.length;
int totalSum = 0;
// generate all subarrays using two nested loops
for (int i = 0; i < n; i++) {
int currentMin = Integer.MAX_VALUE;
int currentMax = Integer.MIN_VALUE;
// extend subarray from index i to j
for (int j = i; j < n; j++) {
// update currentMin and currentMax
// for this subarray
currentMin = Math.min(currentMin, arr[j]);
currentMax = Math.max(currentMax, arr[j]);
// add range of this subarray to totalSum
totalSum += (currentMax - currentMin);
}
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(subarrayRanges(arr));
}
}
def subarrayRanges(arr):
n = len(arr)
totalSum = 0
# generate all subarrays using two nested loops
for i in range(n):
currentMin = float('inf')
currentMax = float('-inf')
# extend subarray from index i to j
for j in range(i, n):
# update currentMin and currentMax
# for this subarray
currentMin = min(currentMin, arr[j])
currentMax = max(currentMax, arr[j])
# add range of this subarray to totalSum
totalSum += (currentMax - currentMin)
return totalSum
if __name__ == "__main__":
arr = [1, 2, 3]
print(subarrayRanges(arr))
using System;
class GfG {
static int subarrayRanges(int[] arr) {
int n = arr.Length;
int totalSum = 0;
// generate all subarrays using two nested loops
for (int i = 0; i < n; i++) {
int currentMin = int.MaxValue;
int currentMax = int.MinValue;
// extend subarray from index i to j
for (int j = i; j < n; j++) {
// update currentMin and currentMax
// for this subarray
currentMin = Math.Min(currentMin, arr[j]);
currentMax = Math.Max(currentMax, arr[j]);
// add range of this subarray to totalSum
totalSum += (currentMax - currentMin);
}
}
return totalSum;
}
// Driver Code
public static void Main(string[] args) {
int[] arr = {1, 2, 3};
Console.WriteLine(subarrayRanges(arr));
}
}
function subarrayRanges(arr) {
let n = arr.length;
let totalSum = 0;
// generate all subarrays using two nested loops
for (let i = 0; i < n; i++) {
let currentMin = Infinity;
let currentMax = -Infinity;
// extend subarray from index i to j
for (let j = i; j < n; j++) {
// update currentMin and currentMax
// for this subarray
currentMin = Math.min(currentMin, arr[j]);
currentMax = Math.max(currentMax, arr[j]);
// add range of this subarray to totalSum
totalSum += (currentMax - currentMin);
}
}
return totalSum;
}
// Driver Code
let arr = [1, 2, 3];
console.log(subarrayRanges(arr));
Output
4
[Expected Approach] Contribution of Each Element using Monotonic Stacks
Instead of calculating the min and max for each subarray individually, we calculate how much each element contributes to the sum of ranges.
For each element in the array:
- Find the number of subarrays where it is the maximum.
- Find the number of subarrays where it is the minimum.
- The contribution of an element to the total sum is: contribution = (count as max - count as min) * element value
- Sum all contributions of every element to get the final answer.
To efficiently find next/previous greater and next/previous smaller elements, we use monotonic stacks.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int subarrayRanges(vector<int>& arr) {
int n = arr.size();
vector<int> leftMin(n), rightMin(n);
vector<int> leftMax(n), rightMax(n);
stack<int> st;
// previous Smaller Element (leftMin)
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] > arr[i]) st.pop();
leftMin[i] = st.empty() ? i + 1 : i - st.top();
st.push(i);
}
while (!st.empty()) st.pop();
// next Smaller Element (rightMin)
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
rightMin[i] = st.empty() ? n - i : st.top() - i;
st.push(i);
}
while (!st.empty()) st.pop();
// previous Greater Element (leftMax)
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] < arr[i]) st.pop();
leftMax[i] = st.empty() ? i + 1 : i - st.top();
st.push(i);
}
while (!st.empty()) st.pop();
// next Greater Element (rightMax)
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && arr[st.top()] <= arr[i]) st.pop();
rightMax[i] = st.empty() ? n - i : st.top() - i;
st.push(i);
}
// calculate total contribution
int totalSum = 0;
for (int i = 0; i < n; i++) {
int maxContri = leftMax[i] * rightMax[i] * arr[i];
int minContri = leftMin[i] * rightMin[i] * arr[i];
totalSum += (maxContri - minContri);
}
return totalSum;
}
int main() {
vector<int> arr = {1, 2, 3};
cout << subarrayRanges(arr) << endl;
return 0;
}
import java.util.Stack;
class GfG {
static int subarrayRanges(int[] arr) {
int n = arr.length;
int[] leftMin = new int[n], rightMin = new int[n];
int[] leftMax = new int[n], rightMax = new int[n];
Stack<Integer> st = new Stack<>();
// previous Smaller Element (leftMin)
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
leftMin[i] = st.isEmpty() ? i + 1 : i - st.peek();
st.push(i);
}
st.clear();
// next Smaller Element (rightMin)
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
rightMin[i] = st.isEmpty() ? n - i : st.peek() - i;
st.push(i);
}
st.clear();
// previous Greater Element (leftMax)
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && arr[st.peek()] < arr[i]) st.pop();
leftMax[i] = st.isEmpty() ? i + 1 : i - st.peek();
st.push(i);
}
st.clear();
// next Greater Element (rightMax)
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && arr[st.peek()] <= arr[i]) st.pop();
rightMax[i] = st.isEmpty() ? n - i : st.peek() - i;
st.push(i);
}
// calculate total contribution
int totalSum = 0;
for (int i = 0; i < n; i++) {
int maxContri = leftMax[i] * rightMax[i] * arr[i];
int minContri = leftMin[i] * rightMin[i] * arr[i];
totalSum += (maxContri - minContri);
}
return totalSum;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(subarrayRanges(arr));
}
}
def subarrayRanges(arr):
n = len(arr)
leftMin = [0] * n
rightMin = [0] * n
leftMax = [0] * n
rightMax = [0] * n
st = []
# previous Smaller Element (leftMin)
for i in range(n):
while st and arr[st[-1]] > arr[i]:
st.pop()
leftMin[i] = i + 1 if not st else i - st[-1]
st.append(i)
st.clear()
# next Smaller Element (rightMin)
for i in range(n - 1, -1, -1):
while st and arr[st[-1]] >= arr[i]:
st.pop()
rightMin[i] = n - i if not st else st[-1] - i
st.append(i)
st.clear()
# previous Greater Element (leftMax)
for i in range(n):
while st and arr[st[-1]] < arr[i]:
st.pop()
leftMax[i] = i + 1 if not st else i - st[-1]
st.append(i)
st.clear()
# next Greater Element (rightMax)
for i in range(n - 1, -1, -1):
while st and arr[st[-1]] <= arr[i]:
st.pop()
rightMax[i] = n - i if not st else st[-1] - i
st.append(i)
# calculate total contribution
totalSum = 0
for i in range(n):
maxContri = leftMax[i] * rightMax[i] * arr[i]
minContri = leftMin[i] * rightMin[i] * arr[i]
totalSum += (maxContri - minContri)
return totalSum
if __name__ == "__main__":
arr = [1, 2, 3]
print(subarrayRanges(arr))
using System;
using System.Collections.Generic;
class GfG {
static int subarrayRanges(int[] arr) {
int n = arr.Length;
int[] leftMin = new int[n], rightMin = new int[n];
int[] leftMax = new int[n], rightMax = new int[n];
Stack<int> st = new Stack<int>();
// previous Smaller Element (leftMin)
for (int i = 0; i < n; i++) {
while (st.Count > 0 && arr[st.Peek()] > arr[i]) st.Pop();
leftMin[i] = st.Count == 0 ? i + 1 : i - st.Peek();
st.Push(i);
}
st.Clear();
// next Smaller Element (rightMin)
for (int i = n - 1; i >= 0; i--) {
while (st.Count > 0 && arr[st.Peek()] >= arr[i]) st.Pop();
rightMin[i] = st.Count == 0 ? n - i : st.Peek() - i;
st.Push(i);
}
st.Clear();
// previous Greater Element (leftMax)
for (int i = 0; i < n; i++) {
while (st.Count > 0 && arr[st.Peek()] < arr[i]) st.Pop();
leftMax[i] = st.Count == 0 ? i + 1 : i - st.Peek();
st.Push(i);
}
st.Clear();
// next Greater Element (rightMax)
for (int i = n - 1; i >= 0; i--) {
while (st.Count > 0 && arr[st.Peek()] <= arr[i]) st.Pop();
rightMax[i] = st.Count == 0 ? n - i : st.Peek() - i;
st.Push(i);
}
// calculate total contribution
int totalSum = 0;
for (int i = 0; i < n; i++) {
int maxContri = leftMax[i] * rightMax[i] * arr[i];
int minContri = leftMin[i] * rightMin[i] * arr[i];
totalSum += (maxContri - minContri);
}
return totalSum;
}
public static void Main(string[] args) {
int[] arr = {1, 2, 3};
Console.WriteLine(subarrayRanges(arr));
}
}
function subarrayRanges(arr) {
let n = arr.length;
let leftMin = new Array(n), rightMin = new Array(n);
let leftMax = new Array(n), rightMax = new Array(n);
let st = [];
// previous Smaller Element (leftMin)
for (let i = 0; i < n; i++) {
while (st.length > 0 && arr[st[st.length - 1]] > arr[i]) st.pop();
leftMin[i] = st.length === 0 ? i + 1 : i - st[st.length - 1];
st.push(i);
}
st = [];
// next Smaller Element (rightMin)
for (let i = n - 1; i >= 0; i--) {
while (st.length > 0 && arr[st[st.length - 1]] >= arr[i]) st.pop();
rightMin[i] = st.length === 0 ? n - i : st[st.length - 1] - i;
st.push(i);
}
st = [];
// previous Greater Element (leftMax)
for (let i = 0; i < n; i++) {
while (st.length > 0 && arr[st[st.length - 1]] < arr[i]) st.pop();
leftMax[i] = st.length === 0 ? i + 1 : i - st[st.length - 1];
st.push(i);
}
st = [];
// next Greater Element (rightMax)
for (let i = n - 1; i >= 0; i--) {
while (st.length > 0 && arr[st[st.length - 1]] <= arr[i]) st.pop();
rightMax[i] = st.length === 0 ? n - i : st[st.length - 1] - i;
st.push(i);
}
// calculate total contribution
let totalSum = 0;
for (let i = 0; i < n; i++) {
let maxContri = leftMax[i] * rightMax[i] * arr[i];
let minContri = leftMin[i] * rightMin[i] * arr[i];
totalSum += (maxContri - minContri);
}
return totalSum;
}
// Driver Code
let arr = [1, 2, 3];
console.log(subarrayRanges(arr));
Output
4
Time Complexity: O(n), each element is pushed and popped from the stack at most once.
Auxiliary Space: O(n), for the stacks used to compute next/previous greater and smaller elements.