leetcode

commit 78be7ecce3b712b5c46b44565bafe910fb5831b4
parent 9c330f567f71a6369e2fe1854e0eaa998d347d6f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  4 Oct 2023 20:36:24 +0000

2 Random Problems

Diffstat:
A
Problems/0907.cpp
 | 
20
++++++++++++++++++++
A
Problems/2104.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 51 insertions(+), 0 deletions(-)
diff --git a/Problems/0907.cpp b/Problems/0907.cpp
@@ -0,0 +1,20 @@
+class Solution {
+    static const int MOD = 1e9 + 7;
+
+  public:
+    int sumSubarrayMins(const vector<int> &arr) {
+        const int n = arr.size();
+        stack<int> st;
+
+        long long res = 0;
+        for (int right = 0, mid, left; right <= n; right++) {
+            while (!st.empty() && (right == n || arr[st.top()] > arr[right])) {
+                mid = st.top(), st.pop();
+                left = st.empty() ? -1 : st.top();
+                res = (res + (long long)arr[mid] * (right - mid) * (mid - left)) % MOD;
+            }
+            st.push(right);
+        }
+        return res;
+    }
+};
diff --git a/Problems/2104.cpp b/Problems/2104.cpp
@@ -0,0 +1,29 @@
+class Solution {
+  public:
+    long long subArrayRanges(const vector<int> &nums) {
+        const int n = nums.size();
+        long long res = 0;
+        stack<int> st;
+
+        for (int right = 0, mid, left; right <= n; right++) {
+            while (!st.empty() && (right == n || nums[st.top()] >= nums[right])) {
+                mid = st.top(), st.pop();
+                left = st.empty() ? -1 : st.top();
+                res -= (long long)nums[mid] * (right - mid) * (mid - left);
+            }
+            st.push(right);
+        }
+
+        st.pop();
+        for (int right = 0, mid, left; right <= n; right++) {
+            while (!st.empty() && (right == n || nums[st.top()] <= nums[right])) {
+                mid = st.top(), st.pop();
+                left = st.empty() ? -1 : st.top();
+                res += (long long)nums[mid] * (right - mid) * (mid - left);
+            }
+            st.push(right);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -446,6 +446,7 @@ for solving problems.
 |  0901  |   Medium   | [Online Stock Span](Problems/0901.cpp)                                                             |
 |  0904  |   Medium   | [Fruit Into Baskets](Problems/0904.cpp)                                                            |
 |  0905  |    Easy    | [Sort Array By Parity](Problems/0905.cpp)                                                          |
+|  0907  |   Medium   | [Sum of Subarray Minimums](Problems/0907.cpp)                                                      |
 |  0909  |   Medium   | [Snakes and Ladders](Problems/0909.cpp)                                                            |
 |  0912  |   Medium   | [Sort an Array](Problems/0912.cpp)                                                                 |
 |  0915  |   Medium   | [Partition Array into Disjoint Intervals](Problems/0915.cpp)                                       |
@@ -745,6 +746,7 @@ for solving problems.
 |  2090  |   Medium   | [K Radius Subarray Averages](Problems/2090.cpp)                                                    |
 |  2095  |   Medium   | [Delete the Middle Node of a Linked List](Problems/2095.cpp)                                       |
 |  2101  |   Medium   | [Detonate the Maximum Bombs](Problems/2101.cpp)                                                    |
+|  2104  |   Medium   | [Sum of Subarray Ranges](Problems/2104.cpp)                                                        |
 |  2115  |   Medium   | [Find All Possible Recipes from Given Supplies](Problems/2115.cpp)                                 |
 |  2120  |   Medium   | [Execution of All Suffix Instructions Staying in a Grid](Problems/2120.cpp)                        |
 |  2125  |   Medium   | [Number of Laser Beams in a Bank](Problems/2125.cpp)                                               |