Sum of Subarray Minimums

Easy

0/40

Contributed by

41 upvotes

Problem statement

You are given an array 'arr' of length ‘N’.

Let ‘X’ be the minimum element of any contiguous subarray of ‘arr’.

You need to return the sum of 'X' over all the contiguous subarrays of 'arr'. Since the answer may be large, you should return it modulo 10^9+7.

A contiguous subarray is a subset of consecutive elements from an array where the elements are adjacent and appear in the same order as in the original array.

Example:

Input:
arr = [1, 2, 3, 4], N = 4

Output:
20

Explanation: Valid contiguous subarrays are [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4]. 
The minimum number in the subarrays are 1, 2, 3, 4, 1, 2, 3, 1, 2 and 1.
The sum of these minimum numbers is 20.
Hence we return 20.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input will contain an integer ‘N’ denoting the length of the array ‘arr’.
The next line contains ‘N’ space-separated integers.

Output Format:-

The only line contains the required sum 'X' %  (10^9 + 7).

Note:-

You don’t need to print anything. Just implement the given function.

Sample Input 1:

3
1 5 3

Sample Output 1:

Explanation Of Sample Input 1:

For test case one:
Input:
arr = [1, 5, 3], N=3
Output:
14
Explanation: Valid contiguous subarrays are [1], [5], [3], [1, 5], [5, 3], and [1, 5, 3]. 
The minimum number in the subarrays are 1, 5, 3, 1, 3, and 1.
The sum of these minimum numbers is 14.
Hence we return 14.

Sample Input 2:

4
5 10 5 10

Sample Output 2:

Constraints:

1 <= N <= 10^5
1 <= arr[i] <= 10^5.
Time Limit: 1 sec

Console