In this guide, you will get 2104. Sum of Subarray Ranges LeetCode Solution with the best time and space complexity. The solution to Sum of Subarray Ranges problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Follow-up: Could you find a solution with O(n) time complexity?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2104. Sum of Subarray Ranges LeetCode Solution in C++
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
const auto [prevGt, nextGt] = getPrevNext(nums, less<>());
const auto [prevLt, nextLt] = getPrevNext(nums, greater<>());
long ans = 0;
for (int i = 0; i < nums.size(); ++i) {
ans += static_cast<long>(nums[i]) * (i - prevGt[i]) * (nextGt[i] - i);
ans -= static_cast<long>(nums[i]) * (i - prevLt[i]) * (nextLt[i] - i);
}
return ans;
}
private:
// Returns `prev` and `next`, that store the indices of the nearest numbers
// that are smaller or larger than the current number depending on `op`.
pair<vector<int>, vector<int>> getPrevNext(
const vector<int>& nums, const function<bool(int, int)>& op) {
const int n = nums.size();
vector<int> prev(n, -1);
vector<int> next(n, n);
stack<int> stack;
for (int i = 0; i < n; ++i) {
while (!stack.empty() && op(nums[stack.top()], nums[i])) {
const int index = stack.top();
stack.pop();
next[index] = i;
}
if (!stack.empty())
prev[i] = stack.top();
stack.push(i);
}
return {prev, next};
}
}; /* code provided by PROGIEZ */
2104. Sum of Subarray Ranges LeetCode Solution in Java
class Solution {
public long subArrayRanges(int[] nums) {
Pair<int[], int[]> gt = getPrevNext(nums, (a, b) -> a < b);
Pair<int[], int[]> lt = getPrevNext(nums, (a, b) -> a > b);
int[] prevGt = gt.getKey();
int[] nextGt = gt.getValue();
int[] prevLt = lt.getKey();
int[] nextLt = lt.getValue();
long ans = 0;
for (int i = 0; i < nums.length; ++i) {
ans += (long) nums[i] * (i - prevGt[i]) * (nextGt[i] - i);
ans -= (long) nums[i] * (i - prevLt[i]) * (nextLt[i] - i);
}
return ans;
}
// Returns `prev` and `next`, that store the indices of the nearest numbers
// that are smaller or larger than the current number depending on `op`.
private Pair<int[], int[]> getPrevNext(int[] nums, BiFunction<Integer, Integer, Boolean> op) {
final int n = nums.length;
int[] prev = new int[n];
int[] next = new int[n];
Arrays.fill(prev, -1);
Arrays.fill(next, n);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && op.apply(nums[stack.peek()], nums[i]))
next[stack.pop()] = i;
if (!stack.isEmpty())
prev[i] = stack.peek();
stack.push(i);
}
return new Pair<>(prev, next);
}
} // code provided by PROGIEZ
2104. Sum of Subarray Ranges LeetCode Solution in Python
class Solution:
def subArrayRanges(self, nums: list[int]) -> int:
prevGt, nextGt = self._getPrevNext(nums, operator.lt)
prevLt, nextLt = self._getPrevNext(nums, operator.gt)
return sum(num * (i - prevGt[i]) * (nextGt[i] - i) -
num * (i - prevLt[i]) * (nextLt[i] - i)
for i, num in enumerate(nums))
def _getPrevNext(
self,
nums: list[int],
op: callable
) -> tuple[list[int], list[int]]:
"""
Returns `prev` and `next`, that store the indices of the nearest numbers
that are smaller or larger than the current number depending on `op`.
"""
n = len(nums)
prev = [-1] * n
next = [n] * n
stack = []
for i, num in enumerate(nums):
while stack and op(nums[stack[-1]], num):
next[stack.pop()] = i
if stack:
prev[i] = stack[-1]
stack.append(i)
return prev, next # code by PROGIEZ
