LeetCode Q 907 - Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1: Input: [3,1,2,4] ; Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Solution

A very good explanation can be found here

Divide this question into two sub-questions, for A[i]

Find the distance beteen A[i] and its Previous Less Element, denoting as left[i].
Find the distance beteen A[i] and its Next Less Element, denoting as left[i].
So the influence area of A[i] is between left[i] and right[i].
Then minSum = Sum(A[i] * left[i] * right[i].

Code

public int sumSubarrayMins(int[] A) {     
  if (A == null || A.length == 0)
    return 0;

  int[] left = new int[A.length];
  int[] right = new int[A.length];

  Stack<Integer> stack = new Stack<>(); // storing the index

  // initialize two arrays
  for (int i = 0; i < A.length; i++) {
    left[i] = i + 1; // how many sub-arrays on its left
    right[i] = A.length - i; // how many sub-arrays on its right
  }

  // find dist between A[i] and its PLE
  for (int i = 0; i < A.length; i++) {
    while (!stack.isEmpty() && A[stack.peek()] > A[i])
      stack.pop();

    left[i] = stack.isEmpty() ? i + 1; i - stack.peek();
    stack.push(i);
  }

  // find dist between A[i] and its NLE
  stack = new Stack<>();
  for (int i = 0; i < A.length; i++) {
    while (!stack.isEmpty() && A[stack.peek()] > A[i]) {
      int index = stack.pop()
      right[index] = i - index;
    }

    stack.push(i);
  }

  int ans = 0;
  int MOD = (int)1e9 + 7;
  for(int i = 0; i < A.length; i++) {
    ans = (ans + A[i] * left[i] * right[i]) % MOD;
  }

  return ans;
}

Reprint policy