aboutsummaryrefslogtreecommitdiff
path: root/sum_subarr_mins.py
diff options
context:
space:
mode:
Diffstat (limited to 'sum_subarr_mins.py')
-rw-r--r--sum_subarr_mins.py28
1 files changed, 28 insertions, 0 deletions
diff --git a/sum_subarr_mins.py b/sum_subarr_mins.py
new file mode 100644
index 0000000..38aeb98
--- /dev/null
+++ b/sum_subarr_mins.py
@@ -0,0 +1,28 @@
+# 907. Sum of Subarray Minimums
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def sumSubarrayMins(self, arr):
+ stack = []
+ ans = 0
+ arr = [float("-inf")] + arr + [float("-inf")]
+ for i, num in enumerate(arr):
+ while stack and arr[stack[-1]] > num:
+ curr = stack.pop()
+ ans += arr[curr] * (i - curr) * (curr - stack[-1])
+ stack.append(i)
+ return ans % (10**9 + 7)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.sumSubarrayMins([3, 1, 2, 4]))
+ # expect: 17
+ print(obj.sumSubarrayMins([11, 81, 94, 43, 3]))
+ # expect: 444