leetcode

commit d9c665c3d6886216c99798d8c52099ff781b5a71
parent 938b692ac94451317ef6757e57f8653fc0de6772
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  7 Jan 2023 15:47:07 +0100

Daily problem + one hard

Diffstat:
A
Problems/0134.cpp
 | 
15
+++++++++++++++
A
Problems/0135.cpp
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/Problems/0134.cpp b/Problems/0134.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
+    int start = 0, total = 0, tank = 0;
+    for (int i = 0; i < gas.size(); i++) {
+      tank = tank + gas[i] - cost[i];
+      if (tank < 0) {
+        start = i + 1;
+        total += tank;
+        tank = 0;
+      }
+    }
+    return (total + tank >= 0) ? start : -1;
+  }
+};
diff --git a/Problems/0135.cpp b/Problems/0135.cpp
@@ -0,0 +1,47 @@
+// original solution - accepted
+class Solution {
+public:
+  int candy(vector<int> &ratings) {
+    // place holder rating for easy neighbor calculation
+    ratings.insert(ratings.begin(), -1), ratings.push_back(-1);
+    int n = ratings.size();
+
+    // sort by rating remembering the original index
+    vector<pair<int, int>> vec;
+    vec.reserve(n);
+    for (int i = 1; i < n - 1; i++) vec.push_back({ratings[i], i});
+    sort(vec.begin(), vec.end());
+
+    vector<int> res(n, 1);        // 'Each child must have at least one candy'
+    res.front() = res.back() = 0; // except placeholders
+    for (auto &[rating, index] : vec) {
+      if (rating < ratings[index + 1])
+        res[index + 1] = max(res[index + 1], res[index] + 1);
+
+      if (rating < ratings[index - 1])
+        res[index - 1] = max(res[index - 1], res[index] + 1);
+    }
+
+    return accumulate(res.begin(), res.end(), 0);
+  }
+};
+
+// improved solution - same logic no nonsense
+class Solution {
+public:
+  int candy(vector<int> &ratings) {
+    int n = ratings.size();
+    if (n <= 1) return n;
+
+    vector<int> res(n, 1);
+    for (int i = 0; i < n - 1; i++) {
+      if (ratings[i] < ratings[i + 1]) res[i + 1] = res[i] + 1;
+    }
+
+    for (int i = n - 1; i > 0; i--) {
+      if (ratings[i] < ratings[i - 1]) res[i - 1] = max(res[i - 1], res[i] + 1);
+    }
+
+    return accumulate(res.begin(), res.end(), 0);
+  }
+};
diff --git a/README.md b/README.md
@@ -76,6 +76,8 @@ for solving problems.
 |  0125  |    Easy    | [Valid Palindrome](Problems/0125.cpp)                                                            |
 |  0129  |   Medium   | [Sum Root to Leaf Numbers](Problems/0129.cpp)                                                    |
 |  0133  |   Medium   | [Clone Graph](Problems/0133.cpp)                                                                 |
+|  0134  |   Medium   | [Gas Station](Problems/0134.cpp)                                                                 |
+|  0135  |    Hard    | [Candy](Problems/0135.cpp)                                                                       |
 |  0138  |   Medium   | [Copy List with Random Pointer](Problems/0138.cpp)                                               |
 |  0141  |    Easy    | [Linked List Cycle](Problems/0141.cpp)                                                           |
 |  0142  |   Medium   | [Linked List Cycle II](Problems/0142.cpp)                                                        |