Sum of the minimum values in subarrays

Easy
0/40
Average time to solve is 15m
profile
Contributed by
14 upvotes
Asked in company
VMware Inc

Problem statement

You are given an array ‘ARR’ containing ‘N’ integers’. The task is to find the sum of the minimum value in ‘SUB’, where ‘SUB’ ranges over every contiguous subarray of ‘ARR.

Example: 
‘ARR = [3, 2, 1, 3]’, ‘N = 4’ 

1. Subarrays with ‘1’ as their minimum value: [1], [2,1], [1,3], [3,2,1], [2,1,3], [3,2,1,3]. Sum = 1 + 1 + 1 + 1 + 1 + 1 = 6.
2. Subarrays with ‘2’ as their minimum value: [2], [3,2]. Sum = 2 + 2 = 4.
3. Subarrays with ‘3’ as their minimum value: [3], [3]. Sum = 3 + 3 = 6.

The sum over all subarrays is ‘6 + 4 + 6 = 16’. Thus, you should return ‘16’ as the answer.
Note : 
1. The answer may be huge, so return the answer modulo ‘10^9 + 7’.
2. You do not need to print anything; it has already been taken care of. Just implement the function.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains an integer ‘N’ denoting the size of the array ‘ARR’.
The second line of each test case contains ‘N’ integers representing the array ‘ARR’.
For more clarity, please refer to the sample inputs.
Output format : 
For every test case, you should return the sum of the minimum value in ‘SUB’, where ‘SUB’ ranges over every contiguous subarray of ‘ARR.
Constraints : 
1 <= T <= 100
1 <= N <= 1000
1 <= Value in each element of ‘ARR’ <= 10^5

Where ‘T’ is the number of test cases, and ‘N’ is the size of the array ‘ARR’.

Time limit: 1 second

Sample input 1 :

2
4
1 2 3 4
4
2 4 4 2

Sample output 1 :

20
26

Explanation of sample input 1 :

Test Case 1 :

1. Subarrays with ‘1’ as their minimum value: [1], [1,2], [1,2,3], [1,2,3,4]. Sum = 1 + 1 + 1 + 1 = 4.
2. Subarrays with ‘2’ as their minimum value: [2], [2,3], [2,3,4]. Sum = 2 + 2 + 2 = 6.
3. Subarrays with ‘3’ as their minimum value: [3], [3,4]. Sum = 3 + 3 = 6.
4. Subarrays with ‘4’ as their minimum value: [4]. Sum = 4.

The sum over all subarrays is ‘4 + 6 + 6 + 4 = 20’. Thus, you should return ‘20’ as the answer.

Test Case 2 :

1. Subarrays with ‘2’ as their minimum value: [2], [2], [2,4], [4,2], [2,4,4], [4,4,2], [2,4,4,2]. Sum = 2 + 2 + 2 + 2 + 2 + 2 + 2 = 14.
2. Subarrays with ‘4’ as their minimum value: [4], [4], [4,4]. Sum = 4 + 4 + 4 = 12.

The sum over all subarrays is ‘14 + 12 = 26’. Thus, you should return ‘26’ as the answer.

Sample input 2 :

2
5
1 3 2 4 2
4
2 1 3 2

Sample output 2 :

28
15
Hint

Try to generate all possible subarrays.

Approaches (3)
Brute force

A simple approach is to use two nested loops to generate all the possible subarrays. We can use a variable local to the outer loop to track the minimum values of the subarrays generated in the inner loop.

 

Algorithm:

  • Set ‘RES = 0’. Use it to store the sum of the minimum values in all subarrays.
  • Set ‘MOD = 10^9 + 7’. To compute the answer modulo ‘10^9 + 7’.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’:
    • Set ‘CUR = ARR[i]’. Use it to store the minimum value in the subarray ‘[i, j]’.
    • Run a loop where ‘j’ ranges from ‘i’ to ‘N-1’ to iterate through all the subarray starting from ‘i’:
      • ‘CUR = min(CUR, ARR[j])’, Update the ‘CUR’.
      • ‘RES = (RES + CUR) % MOD’.
  • Return ‘RES’ as the answer.
Time Complexity

O(N^2), where ‘N’ is the size of the array ‘ARR’.

 

We iterate through all subarrays, and there are ‘N*(N+1)/2’ subarrays. Thus, the time complexity is ‘O(N^2)’.

Space Complexity

O(1),

 

Since we are not using any extra space, space complexity is constant.

Code Solution
(100% EXP penalty)
Sum of the minimum values in subarrays
Full screen
Console