This content originally appeared on DEV Community and was authored by Mostafa Shariare
đź“ť Problem Statement:
Given a mountain array, find the peak index. A mountain array is one where:
- The elements first strictly increase, reaching a peak.
- After the peak, they strictly decrease.
You're tasked with finding the index of that peak element.
Example:
Input: arr = [0, 2, 3, 4, 5, 3, 1]
Output: 4
Here, arr[4] = 5 is the peak element.
🛠️ Approach:
A brute force approach would involve iterating through the array to find the peak by checking when an element is greater than its neighbors. But we can do better.
Since the array is structured like a mountain, with an increasing part followed by a decreasing part, we can leverage binary search to efficiently solve this problem.
The idea is:
- Use binary search to find the peak.
- If the middle element is greater than the next one (
arr[mid] > arr[mid + 1]), this means we're on the descending part of the mountain, so the peak is to the left, includingmid. - Otherwise, the peak is to the right, excluding
mid.
This approach runs in O(log n) time, making it much faster than a linear search.
🔨 Solution Code:
Here's the code to solve the problem using binary search:
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int start = 0;
int end = arr.length - 1;
// Binary Search loop
while (start < end) {
int mid = start + (end - start) / 2;
// If mid is greater than the next element, peak is on the left
if (arr[mid] > arr[mid + 1]) {
end = mid;
} else {
// If mid is less than the next element, peak is on the right
start = mid + 1;
}
}
// Start and end will converge to the peak index
return start;
}
}
🔍 Explanation:
-
Initial Setup:
- We define
startas 0 andendas the last index of the array.
- We define
-
Binary Search:
- The loop continues until
startis equal toend. - We calculate
midas the average ofstartandend. - If the middle element is greater than the next one (
arr[mid] > arr[mid + 1]), this means we are in the descending part of the mountain. So, we moveendtomid, as the peak could still be atmid. - Otherwise, we move
starttomid + 1, as the peak must be in the right part.
- The loop continues until
-
Termination:
- The loop terminates when
start == end, and this index is the peak of the mountain.
- The loop terminates when
⚡ Time Complexity:
The time complexity of this solution is O(log n), where n is the number of elements in the array. This is because we halve the search space in each step, as binary search does.
🎯 Key Takeaways:
- The binary search technique is an efficient way to solve problems when you can leverage the sorted or partially sorted nature of the input.
- Always think about how to reduce time complexity by avoiding brute-force solutions.
- Practice problems like these to improve your algorithmic thinking!
This content originally appeared on DEV Community and was authored by Mostafa Shariare
Mostafa Shariare | Sciencx (2024-09-19T16:49:54+00:00) 🚀 Solving LeetCode 852: Peak Index in a Mountain Array Using Binary Search. Retrieved from https://www.scien.cx/2024/09/19/%f0%9f%9a%80-solving-leetcode-852-peak-index-in-a-mountain-array-using-binary-search/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.