aboutsummaryrefslogtreecommitdiff
path: root/find_peak_element.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_peak_element.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_peak_element.c')
-rw-r--r--find_peak_element.c45
1 files changed, 45 insertions, 0 deletions
diff --git a/find_peak_element.c b/find_peak_element.c
new file mode 100644
index 0000000..9803f70
--- /dev/null
+++ b/find_peak_element.c
@@ -0,0 +1,45 @@
+// 162. Find Peak Element
+#include "leetcode.h"
+
+/*
+ * a peak element is an element that is strictly greater than its neighbours.
+ * given a 0 indexed array 'nums', find a peak element and return its index. if
+ * the array contains multiple peaks, return the index to any of the peaks. you
+ * may imagine that 'nums[-1] = nums[n] = -inf' in other words, an element is
+ * always considered to be strictly greater than a neighbour that is outside the
+ * array. you must write an algorithm that runs in 'O(log n)' time.
+ */
+
+int findPeakElement(int *nums, int numsSize) {
+ if (numsSize == 1)
+ return 0;
+ if (numsSize == 2)
+ return nums[0] > nums[1] ? 0 : 1;
+ int left = 0, right = numsSize - 1, mid;
+ while (left < right) {
+ mid = (left + right) / 2;
+ if (!mid)
+ break;
+ if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
+ return mid;
+ else if (nums[mid] > nums[mid - 1])
+ left = mid + 1;
+ else
+ right = mid - 1;
+ }
+ if (right < numsSize - 1 && right) {
+ if (nums[right] > nums[right + 1] && nums[right] > nums[right - 1])
+ return right;
+ } else if (left < numsSize - 1 && left) {
+ if (nums[left] > nums[left + 1] && nums[left] > nums[left - 1])
+ return left;
+ } else
+ return !left ? left : right;
+ return 0;
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 1}, n2[] = {1, 2, 1, 3, 5, 6, 4};
+ printf("%d\n", findPeakElement(n1, ARRAY_SIZE(n1))); // expect: 2
+ printf("%d\n", findPeakElement(n2, ARRAY_SIZE(n2))); // expect: 5
+}