leetcode

commit f38555de9785165ad62c287062e6d11d41e43ca1
parent 8a0c74ecbb680913f1e071669749337abf824af0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 17 Nov 2024 18:47:44 +0100

Daily Problem

Diffstat:
A
Problems/0862.cpp
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 55 insertions(+), 0 deletions(-)
diff --git a/Problems/0862.cpp b/Problems/0862.cpp
@@ -0,0 +1,54 @@
+// Priority queue
+class Solution {
+  public:
+    int shortestSubarray(const vector<int> &nums, int k) const {
+        const int n = size(nums);
+        long long acc = 0;
+        uint res = -1;
+
+        using type_t = pair<long long, int>;
+        priority_queue<type_t, vector<type_t>, greater<>> pq;
+
+        for (uint i = 0; i < n; i++) {
+            acc += nums[i];
+
+            if (acc >= k) res = min(res, i + 1);
+            while (!pq.empty() && acc - pq.top().first >= k) {
+                res = min(res, i - pq.top().second);
+                pq.pop();
+            }
+
+            pq.emplace(acc, i);
+        }
+
+        return res;
+    }
+};
+
+// Deque optimization
+class Solution {
+  public:
+    int shortestSubarray(const vector<int> &nums, int k) const {
+        static long long prfx[100001];
+        for (int i = 0; i < size(nums); i++) {
+            prfx[i + 1] = prfx[i] + nums[i];
+        }
+
+        uint res = -1;
+        deque<int> dq;
+        for (uint i = 0; i <= size(nums); i++) {
+            while (!dq.empty() && prfx[i] - prfx[dq.front()] >= k) {
+                res = min(res, i - dq.front());
+                dq.pop_front();
+            }
+
+            while (!dq.empty() && prfx[i] <= prfx[dq.back()]) {
+                dq.pop_back();
+            }
+
+            dq.push_back(i);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -614,6 +614,7 @@ reference and a base for solving problems.
 |  0859  |    Easy    | [Buddy Strings](Problems/0859.cpp)                                                                 |
 |  0860  |    Easy    | [Lemonade Change](Problems/0860.cpp)                                                               |
 |  0861  |   Medium   | [Score After Flipping Matrix](Problems/0861.cpp)                                                   |
+|  0862  |    Hard    | [Shortest Subarray with Sum at Least K](Problems/0862.cpp)                                         |
 |  0863  |   Medium   | [All Nodes Distance K in Binary Tree](Problems/0863.cpp)                                           |
 |  0864  |    Hard    | [Shortest Path to Get All Keys](Problems/0864.cpp)                                                 |
 |  0865  |   Medium   | [Smallest Subtree with all the Deepest Nodes](Problems/0865.cpp)                                   |