Every Sublist Min Sum- Google Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    int n = nums.size();
    int pref[n + 1] = {};
    stack<int> s;  // Initialising prefix  array and stack
    int ans = 0, j = 0, mod = 1e9 + 7;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && nums[s.top()] >= nums[i])
            s.pop();  // iterating back till we find an index where the minimum of the list if we go
                      // any further left will change

        if (s.empty())
            j = -1;  // we are calculating j just for calculating the count for which nums[i] will
                     // appear  as minimum in the sublist we have created by going left
        else
            j = s.top();
        s.push(i);

        pref[i + 1] = (pref[j + 1] + (i - j) * nums[i]) %
                      mod;  // here maintaining prefix array--Read the implementation part
        ans = (ans + pref[i + 1]) % mod;
    }
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        int n = nums.length;
        int[] next_smaller = new int[n];
        int[] prev_smaller = new int[n];
        Arrays.fill(next_smaller, n);
        Arrays.fill(prev_smaller, -1);

        // compute and fill in the next_smaller
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < n; i++) {
            int cur = nums[i];
            while (stack.size() > 0 && cur < nums[stack.peek()]) {
                next_smaller[stack.pop()] = i;
            }
            stack.push(i);
        }
        // compute and fill in the prev_smaller
        stack = new Stack();
        for (int i = 0; i < n; i++) {
            int cur = nums[i];
            while (stack.size() > 0 && nums[stack.peek()] > cur) {
                stack.pop();
            }
            if (stack.size() > 0)
                prev_smaller[i] = stack.peek();
            stack.push(i);
        }

        // compute the answer
        long res = 0;
        long mod = (long) 1e9 + 7;
        for (int i = 0; i < n; i++) {
            int subarray_min = nums[i];

            int left_count = i - prev_smaller[i]; // number of greater elements on the left
            int right_count =
                next_smaller[i] - i; // number of greater than or equal to  elements on right
            res = res + (subarray_min * (left_count * right_count)) % mod;
            res = res % mod;
        }
        return (int) res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        ans = 0
        s = []  # stack of (index, value, sum)
        currentSum = 0
        for index, value in enumerate(nums):
            while s and value <= s[-1][1]:
                currentSum -= s[-1][2]
                s.pop()
            if not s:
                s.append([index, value, (index + 1) * value])
            else:
                s.append([index, value, (index - s[-1][0]) * value])
            currentSum += s[-1][2]
            ans += currentSum
        return ans % (10 ** 9 + 7)