leetcode

commit b6970a28a0b14b8d0923fb398d36acca71ff439c
parent 529a210ad051b5721494155ade76c0c8432abecd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 12 Oct 2023 15:10:34 +0000

Daily Problem

Diffstat:
M
Problems/1095.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++------
M
README.md
 | 
1
+

2 files changed, 45 insertions(+), 6 deletions(-)
diff --git a/Problems/1095.cpp b/Problems/1095.cpp
@@ -1,10 +1,48 @@
-#include <cmath>
 class Solution {
+    int find_peak(MountainArray &mountainArr) {
+        int left = 1, right = mountainArr.length() - 2;
+        while (left != right) {
+            const int mid = left + (right - left) / 2;
+            if (mountainArr.get(mid) < mountainArr.get(mid + 1))
+                left = mid + 1;
+            else
+                right = mid;
+        }
+        return left;
+    }
+
+    int find_left(MountainArray &mountainArr, int left, int right, int target) {
+        while (left != right) {
+            const int mid = left + (right - left) / 2;
+            if (mountainArr.get(mid) < target)
+                left = mid + 1;
+            else
+                right = mid;
+        }
+        return left;
+    }
+
+    int find_right(MountainArray &mountainArr, int left, int right, int target) {
+        while (left != right) {
+            const int mid = left + (right - left) / 2;
+            if (mountainArr.get(mid) > target)
+                left = mid + 1;
+            else
+                right = mid;
+        }
+        return left;
+    }
+
   public:
-    int findNumbers(vector<int> &nums) {
-        int res = 0;
-        for (int i : nums)
-            if (int(log10(i) + 1) % 2 == 0) res++;
-        return res;
+    int findInMountainArray(int target, MountainArray &mountainArr) {
+        const int peak = find_peak(mountainArr);
+
+        const int left = find_left(mountainArr, 0, peak, target);
+        if (mountainArr.get(left) == target) return left;
+
+        const int right = find_right(mountainArr, peak + 1, mountainArr.length() - 1, target);
+        if (mountainArr.get(right) == target) return right;
+
+        return -1;
     }
 };
diff --git a/README.md b/README.md
@@ -515,6 +515,7 @@ for solving problems.
 |  1090  |   Medium   | [Largest Values From Labels](Problems/1090.cpp)                                                    |
 |  1091  |   Medium   | [Shortest Path in Binary Matrix](Problems/1091.cpp)                                                |
 |  1095  |    Easy    | [Find Numbers with Even Number of Digits](Problems/1095.cpp)                                       |
+|  1095  |    Hard    | [Find in Mountain Array](Problems/1095.cpp)                                                        |
 |  1099  |    Easy    | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)                          |
 |  1104  |   Medium   | [Path In Zigzag Labelled Binary Tree](Problems/1104.cpp)                                           |
 |  1109  |   Medium   | [Corporate Flight Bookings](Problems/1109.cpp)                                                     |