leetcode - 907. 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 10^9 + 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 * 10^4
1 <= arr[i] <= 3 * 10^4

Solution

Solved after help…

The most straightforward way would be: find all the sub arrays, and sum the minimum value. But this way the time complexity would be $o(n^2)$, which is not feasible for this question.

So I think about we could choose each element as the minimum, and expand to left and to right from the element. Until we find the smaller element, keep expanding.

To find the less element from left and from right, we could use monotonic stack.

After finding the less elements, let’s say, left_less and right_less keep the index for the first less element of the current element. Then the number of subarray is (n+1)*n//2, where n is the number of elements in between left_less[i] and right_less[i]. But we need to calculate the number of sub array that contains arr[i], so we could subtract the sub arrays that are at the left of i, and the sub arrays that are at the right of i.

  -1,0,1,2,3,4,5,6,7,8,9
	[2,3,5,7,9,4,7,8,4]
     |		   |	   |
left_less	cur_ele	right_less

As showed above, the number of elements should be 8, and the number of elements at the left should be 4, the number of elements at the right should be 3.

So the number of sub arrays that contains 4 is: $8\ast (8+1)//2-4\ast (4+1)//2-3\ast (3+1)//2$

But, there will be some duplicates, for example: arr=[71,55,82,55], then for the first 55, the subarray will contain [71,55,82,55], and for the second 55 it will also contain this subarray.

To deal with the duplicates, make left_less and right_less strictly less and non-strictly less respectively.

Time complexity: $o(n)$
Space complexity: $o(n)$

Code

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        left_less = []
        mono_stack = []
        for i in range(len(arr)):
            while mono_stack and arr[mono_stack[-1]] >= arr[i]:
                mono_stack.pop()
            if mono_stack:
                left_less.append(mono_stack[-1])
            else:
                left_less.append(-1)
            mono_stack.append(i)
        right_less = []
        mono_stack = []
        for i in range(len(arr) - 1, -1, -1):
            while mono_stack and arr[mono_stack[-1]] > arr[i]:
                mono_stack.pop()
            if mono_stack:
                right_less.append(mono_stack[-1])
            else:
                right_less.append(len(arr))
            mono_stack.append(i)
        right_less = right_less[::-1]
        res = 0
        mod_val = 1000000007
        whole_list = False
        for i in range(len(arr)):
            num_of_ele = right_less[i] - left_less[i] - 1
            num_of_ele_left = i - left_less[i] - 1
            num_of_ele_right = right_less[i] - i - 1
            num_of_subarr = (num_of_ele + 1) * num_of_ele // 2
            num_of_subarr_left = (num_of_ele_left + 1) * num_of_ele_left // 2
            num_of_subarr_right = (num_of_ele_right + 1) * num_of_ele_right // 2
            res += arr[i] * (num_of_subarr - num_of_subarr_left - num_of_subarr_right)
            res %= mod_val
        return res