Given an integer array arr of size N. The Range of a subarray of arr is the difference between the largest and smaller element in the subarray.  
Return the sum of all subarray ranges of arr.
Example 1:
Input:
N = 3
arr[ ] = {1, 2, 3}
Output: 4
Explanation: The 6 subarrays of arr 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
sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4
 
Example 2:
Input:
N = 4
arr[ ] = {-32, 0, -2, 72}
Output: 318
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function subarrayRanges() which takes the array of integers arr and N as parameters and returns a sum of all subarrays ranges of arr.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
10^{-9 }≤ arr_{i  }≤ 10^{-9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def subarrayRanges(self, N, arr):

        # Code here

Solutions:
class Solution:

	def subarrayRanges(self, N, arr):
		res = 0
		(min_stack, max_stack) = ([], [])
		n = len(arr)
		arr.append(0)
		for (i, num) in enumerate(arr):
			while min_stack and (i == n or num < arr[min_stack[-1]]):
				top = min_stack.pop()
				starts = top - min_stack[-1] if min_stack else top + 1
				ends = i - top
				res -= starts * ends * arr[top]
			min_stack.append(i)
			while max_stack and (i == n or num > arr[max_stack[-1]]):
				top = max_stack.pop()
				starts = top - max_stack[-1] if max_stack else top + 1
				ends = i - top
				res += starts * ends * arr[top]
			max_stack.append(i)
		return res


class Solution:

	def subarrayRanges(self, n, arr):
		prev = [-1] * n
		res = [0] * n
		st = []
		for i in range(n):
			while st and arr[st[-1]] > arr[i]:
				st.pop()
			if st:
				prev[i] = st[-1]
			st.append(i)
		for i in range(n):
			index = res[prev[i]] or 0
			res[i] = index + (i - prev[i]) * arr[i]
		mins = sum(res)
		prev = [-1] * n
		res = [0] * n
		st = []
		for i in range(n):
			while st and arr[st[-1]] < arr[i]:
				st.pop()
			if st:
				prev[i] = st[-1]
			st.append(i)
		for i in range(n):
			index = res[prev[i]] or 0
			res[i] = index + (i - prev[i]) * arr[i]
		maxs = sum(res)
		return maxs - mins


class Solution:

	def subarrayRanges(self, n, a):
		stk = []
		a1 = []
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and a[i] <= a[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				a1.append(n)
			else:
				a1.append(stk[-1])
			stk.append(i)
		a1 = a1[::-1]
		stk = []
		a2 = []
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and a[i] >= a[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				a2.append(n)
			else:
				a2.append(stk[-1])
			stk.append(i)
		a2 = a2[::-1]
		b = a[::-1]
		stk = []
		a3 = []
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and b[i] < b[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				a3.append(n)
			else:
				a3.append(stk[-1])
			stk.append(i)
		stk = []
		a4 = []
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and b[i] > b[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				a4.append(n)
			else:
				a4.append(stk[-1])
			stk.append(i)
		for i in range(n):
			a1[i] = a1[i] - i - 1
			a2[i] = a2[i] - i - 1
			a3[i] = a3[i] - (n - i)
			a4[i] = a4[i] - (n - i)
		ans1 = 0
		ans2 = 0
		for i in range(n):
			ans1 += ((a1[i] + 1) * (a3[i] + 1) - 1) * a[i]
			ans2 += ((a2[i] + 1) * (a4[i] + 1) - 1) * a[i]
		return ans2 - ans1


from typing import List

class Solution:

	def subarrayRanges(self, N: int, arr) -> int:
		res = 0
		inc = []
		dec = []
		for i in range(N + 1):
			while inc and (i == N or arr[inc[-1]] < arr[i]):
				curIndex = inc.pop()
				left = inc[-1] if inc else -1
				right = i
				res += (curIndex - left) * (right - curIndex) * arr[curIndex]
			while dec and (i == N or arr[dec[-1]] > arr[i]):
				curIndex = dec.pop()
				left = dec[-1] if dec else -1
				right = i
				res -= (curIndex - left) * (right - curIndex) * arr[curIndex]
			inc.append(i)
			dec.append(i)
		return res


class Solution:

	def subarrayRanges(self, N, nums):
		(n, answer) = (len(nums), 0)
		stack = []
		for right in range(n + 1):
			while stack and (right == n or nums[stack[-1]] <= nums[right]):
				mid = stack.pop()
				left = -1 if not stack else stack[-1]
				answer += nums[mid] * (mid - left) * (right - mid)
			stack.append(right)
		stack.clear()
		for right in range(n + 1):
			while stack and (right == n or nums[stack[-1]] >= nums[right]):
				mid = stack.pop()
				left = -1 if not stack else stack[-1]
				answer -= nums[mid] * (mid - left) * (right - mid)
			stack.append(right)
		return answer


class Solution:

	def all_min(self, arr, n):
		left = [None] * n
		right = [None] * n
		s1 = []
		s2 = []
		for i in range(n):
			cnt = 1
			while s1 and s1[-1][0] > arr[i]:
				cnt += s1[-1][1]
				s1.pop()
			s1.append([arr[i], cnt])
			left[i] = cnt
		for i in range(n - 1, -1, -1):
			cnt = 1
			while s2 and s2[-1][0] >= arr[i]:
				cnt += s2[-1][1]
				s2.pop()
			s2.append([arr[i], cnt])
			right[i] = cnt
		ans = 0
		for i in range(n):
			ans += arr[i] * left[i] * right[i]
		return ans

	def all_max(self, arr, n):
		left = [None] * n
		right = [None] * n
		s1 = []
		s2 = []
		for i in range(n):
			cnt = 1
			while s1 and s1[-1][0] < arr[i]:
				cnt += s1[-1][1]
				s1.pop()
			s1.append([arr[i], cnt])
			left[i] = cnt
		for i in range(n - 1, -1, -1):
			cnt = 1
			while s2 and s2[-1][0] <= arr[i]:
				cnt += s2[-1][1]
				s2.pop()
			s2.append([arr[i], cnt])
			right[i] = cnt
		ans = 0
		for i in range(n):
			ans += arr[i] * left[i] * right[i]
		return ans

	def subarrayRanges(self, N, arr):
		return self.all_max(arr, N) - self.all_min(arr, N)


class Solution:

	def subarrayRanges(self, N, arr):
		(min_L, min_R, max_L, max_R, stack1, stack2) = ([], [], [], [], [], [])
		m = 10 ** 9 + 7
		for i in range(len(arr)):
			count = 1
			while stack1 and stack1[-1][0] > arr[i]:
				count = count + stack1[-1][1]
				stack1.pop()
			min_L.append(count)
			stack1.append((arr[i], count))
			count = 1
			while stack2 and stack2[-1][0] < arr[i]:
				count = count + stack2[-1][1]
				stack2.pop()
			max_L.append(count)
			stack2.append((arr[i], count))
		(stack1, stack2) = ([], [])
		for i in range(len(arr) - 1, -1, -1):
			count = 1
			while stack1 and stack1[-1][0] >= arr[i]:
				count = count + stack1[-1][1]
				stack1.pop()
			min_R.append(count)
			stack1.append((arr[i], count))
			count = 1
			while stack2 and stack2[-1][0] <= arr[i]:
				count = count + stack2[-1][1]
				stack2.pop()
			max_R.append(count)
			stack2.append((arr[i], count))
		min_R.reverse()
		max_R.reverse()
		diff = 0
		for i in range(len(arr)):
			diff = diff + arr[i] * max_L[i] * max_R[i] - arr[i] * min_L[i] * min_R[i]
		return diff


class Solution:

	def subarrayRanges(self, N, arr):
		stack = []
		maxi = 0
		for item in arr:
			count = 0
			while stack and stack[-1][0] < item:
				(stack_item, stack_count) = stack.pop()
				maxi += stack_item * stack_count * count
				count += stack_count
			count += 1
			maxi += count * item
			stack.append((item, count))
		count = 0
		for item in reversed(stack):
			(stack_item, stack_count) = stack.pop()
			maxi += stack_item * stack_count * count
			count += stack_count
		stack = []
		mini = 0
		for item in arr:
			count = 0
			while stack and stack[-1][0] > item:
				(stack_item, stack_count) = stack.pop()
				mini += stack_item * stack_count * count
				count += stack_count
			count += 1
			mini += count * item
			stack.append((item, count))
		count = 0
		for item in reversed(stack):
			(stack_item, stack_count) = stack.pop()
			mini += stack_item * stack_count * count
			count += stack_count
		return maxi - mini


class Solution:

	def subarrayRanges(self, N, arr):
		nums = arr
		(minSum, maxSum) = (0, 0)
		(stack, n) = ([], len(nums))
		for nextSmaller in range(n + 1):
			while len(stack) > 0 and (nextSmaller == n or nums[stack[-1]] > nums[nextSmaller]):
				i = stack.pop()
				prevSmaller = -1 if stack == [] else stack[-1]
				minSum += nums[i] * (nextSmaller - i) * (i - prevSmaller)
			stack.append(nextSmaller)
		stack = []
		for nextGreater in range(n + 1):
			while stack and (nextGreater == n or nums[stack[-1]] < nums[nextGreater]):
				i = stack.pop()
				prevGreater = -1 if stack == [] else stack[-1]
				maxSum += nums[i] * (nextGreater - i) * (i - prevGreater)
			stack.append(nextGreater)
		return maxSum - minSum