0907. Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums

Description

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

Example 1:

**Input:** arr = [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.

Example 2:

**Input:** arr = [11,81,94,43,3]
**Output:** 444

Constraints:

• 1 <= arr.length <= 3 * 104

• 1 <= arr[i] <= 3 * 104

ac: Monotoic queue

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int[] PLE = new int[arr.length]; // Number of previous larger element
        int[] NLE = new int[arr.length]; // Number of next larger element
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int largerIndex = stack.pop();
                NLE[largerIndex] = i - largerIndex - 1;
            }
            PLE[i] = stack.isEmpty() ? i : i - stack.peek() - 1;
            stack.push(i);
        }
        
        // There are remaining elements in stack, e.g. [1,2,3,4,5]
        while (!stack.isEmpty()) {
            int index = stack.pop();
            NLE[index] = arr.length - index - 1;
        }
        
        long sum = 0;
        long MOD = (long) 1e9 + 7;
        for (int i = 0; i < arr.length; i++) {
            // See below explanation to calculate number of subarray.
            long subarrayCount = (PLE[i] + 1) * (NLE[i] + 1);
            sum = (sum + subarrayCount * arr[i]) % MOD;
        }
        
        return (int) sum;
    }
}

/*
O(N) time, O(N) space.

The number of subarrays with 3 in it will be anything that starts in [L..3] and ends in [3..R]. So we have [L..3] starting positions and [3..R] ending positions. 
In other words, we have d1 starting positions and d2 ending positions. So the total number of subarrays is just d1*d2.

For example:
in [9,7,8,3,4,6]
we have 4 choices to start with (9,7,8,3)
we have 3 choices to end with (3,4,6)

So answer is just 4*3.
*/