907. Sum of Subarray Minimums.md

907. Sum of Subarray Minimums

Question

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

• Method 1: Brutal force O(N^2)

   class Solution {
   	public int sumSubarrayMins(int[] A) {
   		if(A == null || A.length == 0) return 0;
   		long sum = 0;
   		for(int i = 0; i < A.length; i++){
   			int min = A[i];
   			for(int j = i; j < A.length; j++){
   				min = Math.min(A[j], min);
   				sum += min;
   			}
   		}
   		return (int)(sum % (Math.pow(10, 9) + 7));
   	}
   }

• Method 2: Monotic stack

  1. How many times a number will appear in the results(Not thinking about minimum)
  • for a element A[i], it will represents (i + 1) * (len - i + 1) times.
  • i + 1 means the subarrays whose end point is A[i]
  • (len - i + 1) means the subarrays whose start point is A[i].
  2. How to solve this question:
  • res = sum(A[i] * f[i], A[i] is the number and f[i] means the number of subarrays where A[i] is the minimum in the subarray.
  • f[i] = left[i] * right[i], where left[i] is the left subarray numbers where A[i] is the last element and A[i] is minimum in current array and right[i] is the minimum and first element in the subarray.
  • How to get left[i] and right[i]. Consider leetcode question 901.
  • We need to consider a corner case, two elements have the same value.

class Solution {
    private static class Pair{
        int val;
        int count;
        public Pair(int val, int count){
            this.val = val;
            this.count = count;
        }
    }
    public int sumSubarrayMins(int[] A) {
        if(A == null || A.length == 0) return 0;
        Stack<Pair> left = new Stack<>();
        int[] leftArr = new int[A.length];
        Stack<Pair> right = new Stack<>();
        int[] rightArr = new int[A.length];
        for(int i = 0; i < A.length; i++){
            int count = 1;
            while(!left.isEmpty() && A[i] < left.peek().val){
                count += left.pop().count;
            }
            left.push(new Pair(A[i], count));
            leftArr[i] = count;
        }
        for(int i = A.length - 1; i >= 0; i--){
            int count = 1;
            while(!right.isEmpty() && A[i] <= right.peek().val){
                count += right.pop().count;
            }
            right.push(new Pair(A[i], count));
            rightArr[i] = count;
        }
        long res = 0;
        for(int i = 0; i < A.length; i++){
            res += A[i] * leftArr[i] * rightArr[i];
        }
        return (int)(res % (1e9 + 7));
    }
}