leetcode

commit 67ecf731b5e0e4e8a23b30e9d47c07b222e42568
parent dbd05c3b893bc9de37d63b9903a90463d6e20f4a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  1 Mar 2023 12:43:49 +0100

Random Problem

Diffstat:
A
Problems/0915.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0915.cpp b/Problems/0915.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+  int partitionDisjoint(vector<int> &nums) {
+    int n = nums.size();
+    vector<int> left(n), right(n);
+
+    left[0] = nums[0];
+    right.back() = nums.back();
+    for (int i = 1; i < nums.size(); i++) {
+      left[i] = max(nums[i], left[i - 1]);
+      right[n - i - 1] = min(nums[n - i - 1], right[n - i]);
+    }
+
+    for (int i = 0; i < n - 1; i++)
+      if (left[i] <= right[i + 1]) return i + 1;
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -329,6 +329,7 @@ for solving problems.
 |  0905  |    Easy    | [Sort Array By Parity](Problems/0905.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)                                                 |
 |  0918  |   Medium   | [Maximum Sum Circular Subarray](Problems/0918.cpp)                                               |
 |  0926  |   Medium   | [Flip String to Monotone Increasing](Problems/0926.cpp)                                          |
 |  0931  |   Medium   | [Minimum Falling Path Sum](Problems/0931.cpp)                                                    |