Sum of Subarray Minimums
Paytm
PhonePeThe problem
Given an array of integers arr of size n, calculate the sum of the minimum value in each (contiguous) subarray of arr. Since the result may be large, return the answer modulo 109 +7.
Input: arr = [3, 1, 2, 5] Output: 18 Explanation: The minimum of subarrays: [3], [1], [2], [5], [3, 1], [1, 2], [2, 5], [3, 1, 2], [1, 2, 5], [3, 1, 2, 5] are 3, 1, 2, 5, 1, 1, 2, 1, 1, 1 respectively and their sum is 18.
Input: arr = [2, 3, 1] Output: 10 Explanation: The minimum of subarrays: [2], [3], [1], [2,3], [3,1], [2,3,1] are 2, 3, 1, 2, 1, 1 respectively and their sum is 10.
Input: arr = [11, 81, 94, 43, 3]
- 1 <= arr.length <= 105
- 1 <= arr[i] <= 106
cpp
class Solution {
public:
int sumSubarrayMins(vector<int> &arr) {
}
};java
class Solution {
public int sumSubarrayMins(int[] arr) {
}
}python
class Solution:
def sumSubarrayMins(self, arr):javascript
class Solution {
sumSubarrayMins(arr) {
}
}csharp
class Solution {
public int SumSubarrayMins(int[] arr) {
}
}go
func sumSubarrayMins(arr []int) int {
}Stuck? Show a way to structure it+
- 01For each element, find how far it can extend left and right while remaining the chosen minimum.
- 02Use asymmetric strict and non-strict comparisons so equal minima are owned once.
- 03Add value times left choices times right choices modulo the required constant.
- 04Use strict comparison on one boundary and non-strict comparison on the other.
Reference answer
Then expect these follow-ups
Why must duplicate tie handling be asymmetric?
Tests: counting correctness
How would you compute the sum of subarray maximums?
Tests: pattern transfer
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question