Sum of the minimum values in subarrays

A simple approach is to use two nested loops to generate all the possible subarrays. We can use a variable local to the outer loop to track the minimum values of the subarrays generated in the inner loop.

Algorithm:

• Set ‘RES = 0’. Use it to store the sum of the minimum values in all subarrays.
• Set ‘MOD = 10^9 + 7’. To compute the answer modulo ‘10^9 + 7’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’:
  • Set ‘CUR = ARR[i]’. Use it to store the minimum value in the subarray ‘[i, j]’.
  • Run a loop where ‘j’ ranges from ‘i’ to ‘N-1’ to iterate through all the subarray starting from ‘i’:
    • ‘CUR = min(CUR, ARR[j])’, Update the ‘CUR’.
    • ‘RES = (RES + CUR) % MOD’.
• Return ‘RES’ as the answer.

We have two array’s ‘LEFT’ and ‘RIGHT’, such that:

• ‘LEFT[i]’ is the number of contiguous values to the left of ‘ARR[i]’ that are strictly greater than ‘ARR[i]’.
• ‘RIGHT[i]’ is the number of contiguous values to the right of ‘ARR[i]’ that is greater than or equal to ‘ARR[i]’.

Then, ‘LEFT[i] + 1’ is the number of subarrays ending with ‘ARR[i]’, where ‘ARR[i]’ is the only minimum value. ‘RIGHT[i] + 1’ is the number of subarrays starting with ‘ARR[i]’, where ‘ARR[i]’ is the first minimum value.

The number of subarrays where ‘ARR[i]’ is the first minimum value will be ‘(LEFT[i] + 1) * (RIGHT[i] + 1)’. The final answer will be summation of ‘(ARR[i] * (LEFT[i] + 1) * (RIGHT[i] + 1))’ where ‘i’ ranges from ‘0’ to ‘N-1’.

We can compute the arrays ‘LEFT’ and ‘RIGHT’ efficiently using a stack. Let’s see how to compute the array ‘LEFT’. We traverse ‘ARR’ using ‘i’ that ranges from ‘0’ to ‘N-1’, and for the current index ‘i’, the stack stores the indexes from ‘0’ to ‘i-1’. The stack doesn’t store all the values from ‘0’ to ‘i-1’. The bottom of the stack is the index of the rightmost smallest value from ‘0’ to ‘i - 1’, let’s say ‘j’. The value above it is the index of the rightmost smallest value from ‘j+1’ to ‘i-1’, and so on. If ‘ARR[i]’ is greater than the top of the stack then ‘LEFT[i] = 1’. Otherwise, if ‘ARR[i]’ is smaller than the top of the stack (let’s say index ‘j’), then it is also smaller than the indexes from ‘j - LEFT[j]’ to ‘j’, so ‘LEFT[i] = LEFT[j] + 1’. Now, pop ‘j’ from the stack. But, if ‘ARR[i]’ is still smaller than the top of the stack, then it is also smaller than the indexes from ‘j - LEFT[j]’ to ‘j’ (‘j’ being the top of the stack). So, ‘LEFT[i] += LEFT[j] + 1’. So, pop all the elements greater than ‘ARR[i]’ from the stack.  After that, push ‘i’ to the stack and continue this process until ‘i’ is not equal to ‘N’.

Consider the following example that illustrates how to compute the array ‘LEFT’:

‘ARR = [20, 10, 20, 30, 10]’

Here, ‘LEFT = [0, 1, 0, 0, 2]’

Similarly, we can compute the array ‘RIGHT’. For computing ‘RIGHT’, traverse the array in reverse and pop the stack even when ‘ARR[i]’ is equal to the top of the stack.

Algorithm:

• Set ‘RES = 0’. Use it to store the sum of the minimum values in all subarrays.
• Set ‘MOD = 10^9 + 7’. To compute the answer modulo ‘10^9 + 7’.
• Create two arrays, ‘LEFT[N]’ and ‘RIGHT[N]’.
• Create a stack ‘ST1’ to compute the array ‘LEFT’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’:
  • Set ‘LEFT[i] = 0’.
  • Run a loop while (‘ST1’ is not empty) and (‘ARR[ST1.top()] is greater than ARR[i]’):
    • ‘LEFT[i] += LEFT[ST1.top()] + 1’
    • Pop the top value from ‘ST1’.
  • ‘ST1.push(i)’
• Create a stack ‘ST2’ to compute the array ‘RIGHT’.
• Run a loop where ‘i’ ranges from ‘N-1’ to ‘0’:
  • Set ‘RIGHT[i] = 0’.
  • Run a loop while (‘ST2’ is not empty) and (‘ARR[ST2.top()] greater than or equal to ARR[i]’):
    • ‘RIGHT[i] += RIGHT[ST2.top()] + 1’
    • Pop the top value from ‘ST2’.
  • ‘ST2.push(i)’
• Set ‘RES = 0’. Use to store the final answer.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’:
  • ‘RES = (RES + ARR[i] * (LEFT[i] + 1) * (RIGHT[i] + 1)) % MOD’
• Return ‘RES’ as the answer.

In the previous approach, while computing the ‘LEFT’ array, the index ‘i’ which pops the top of the stack (let’s say index ‘j’) such that ‘ARR[i] < ARR[j]’ can give us the value of ‘RIGHT[j] + 1’, which will be ‘i - j’. Similarly, the index below the index ‘j’ in the stack can give us the value of ‘LEFT[j] + 1’. Pop ‘j’ from the stack and let ‘k’ be the current top of stack, so ‘LEFT[j] + 1 = j - k’ (if stack is empty set ‘k = -1’ not ‘0’, as we have to find ‘LEFT[j] + 1’). The contribution of ‘j’ to the final answer will be ‘ARR[j] * (i - j) * (j - k)’ (proved in the previous approach).

Some previous indexes might still be remaining in the stack along with the last index, ‘N-1’ (which is at the top), so we have to compute their contribution to the final answer separately. For that use ‘i = N’, this is a boundary case similar to using ‘k = -1’ for an empty stack.

Algorithm:

• Set ‘RES = 0’, Use it to store the sum of the minimum values in all subarrays.
• Set ‘MOD = 10^9 + 7’. To compute the answer modulo ‘10^9 + 7’.
• Create a stack ‘ST’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’:
  • Run a loop while (‘ST’ is not empty) and (‘ARR[ST.top()] is greater than ARR[i]’):
    • ‘j = ST.top()’
    • Pop the top value from ‘ST’.
    • Set ‘k = -1’.
    • If ‘ST’ is not empty, then:
      • Set ‘k = ST.top()’. This is the index of the rightmost value smaller than ‘ARR[j]’.
    • ‘RES = (RES + ARR[j] * (i - j) * (j - k)) % MOD’. The contribution of index ‘ARR[j]’ to the final answer or the number of times ‘ARR[j]’ is the minimum value in a subarray.
  • ‘ST.push(i)’
• Run a loop while (‘ST’ is not empty) to find the contribution of the indexes remaining in the stack to the final answer:
  • ‘j = ST.top()’
  • Pop the top value from ‘ST’.
  • Set ‘k = -1’.
  • If ‘ST’ is not empty, then:
    • Set ‘k = ST.top()’. This is the index of the rightmost value smaller than ‘ARR[j]’.
  • ‘RES = (RES + ARR[j] * (n - j) * (j - k)) % MOD’
• Return ‘RES’ as the answer.