grid47 Exploring patterns and algorithms
Oct 21, 2024
6 min read
Solution to LeetCode 162: Find Peak Element Problem
You are given a list of integers, nums. A peak element is an element that is strictly greater than its neighbors. You need to find and return the index of any peak element in the list. The algorithm should run in O(log n) time.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of integers, nums. The list has at least one element.
Example: [1, 3, 2, 1]
Constraints:
• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.
Output: The output should be the index of any peak element in the list.
Example: 1
Constraints:
• There will always be at least one peak element in the array.
Goal: The goal is to find the peak element index in O(log n) time.
Steps:
• Perform a binary search to find the peak element.
• Check if the middle element is greater than its neighbors.
• If the middle element is a peak, return its index.
• If the left neighbor is greater, search the left half of the array.
• If the right neighbor is greater, search the right half of the array.
Goal: The array length will always be at least 1, and there will always be at least one peak element.
Steps:
• The array will have at least one peak element.
• The algorithm must run in O(log n) time.
Assumptions:
• The array will always contain at least one peak element.
• Input: [1, 3, 2, 1]
• Explanation: In this example, the element 3 is the peak element as it is greater than its neighbors 1 and 2. Therefore, the function returns index 1.
Approach: We will use binary search to find a peak element in the array. Binary search will allow us to find the peak in O(log n) time.
Observations:
• A peak is an element greater than its neighbors.
• Binary search can help us efficiently narrow down the peak element.
• Since we are only asked to find any peak, binary search will efficiently locate one in O(log n) time.
Steps:
• Initialize two pointers, left and right, pointing to the start and end of the array.
• While left <= right, find the middle element.
• Check if the middle element is greater than its neighbors.
• If the middle element is a peak, return its index.
• If the left neighbor is greater, move the right pointer to mid-1 to search the left half.
• If the right neighbor is greater, move the left pointer to mid+1 to search the right half.
Empty Inputs:
• The input will always have at least one element.
Large Inputs:
• The solution should work efficiently for arrays of up to 1000 elements.
Special Values:
• Handle arrays where elements are strictly increasing or strictly decreasing.
Constraints:
• Ensure the algorithm runs in O(log n) time.
intfindPeakElement(vector<int>& arr) {
int n = arr.size();
int l =0, r = n -1;
while(l <= r) {
int mid = l + (r - l) /2;
bool x = mid >0? arr[mid -1] < arr[mid] :true;
bool y = mid < n -1? arr[mid +1] < arr[mid] :true;
if(x && y) return mid;
if(!x && y) r = mid -1;
elseif(x &&!y) l = mid +1;
else r = mid -1;
}
return l;
}
1 : Function Definition
intfindPeakElement(vector<int>& arr) {
Define the function 'findPeakElement' which takes a vector of integers as input and returns the index of a peak element.
2 : Variable Declaration
int n = arr.size();
Declare and initialize 'n' to store the size of the input array 'arr'.
3 : Variable Initialization
int l =0, r = n -1;
Initialize two variables 'l' and 'r' to represent the left and right boundaries of the search space.
4 : Loop
while(l <= r) {
Start a while loop to perform binary search, continuing as long as the left boundary is less than or equal to the right boundary.
5 : Variable Calculation
int mid = l + (r - l) /2;
Calculate the middle index 'mid' using the formula to avoid overflow.
6 : Boolean Expression
bool x = mid >0? arr[mid -1] < arr[mid] :true;
Check if the current element is greater than its left neighbor, or if it's the first element (in which case it is treated as a peak).
7 : Boolean Expression
bool y = mid < n -1? arr[mid +1] < arr[mid] :true;
Check if the current element is greater than its right neighbor, or if it's the last element (in which case it is treated as a peak).
8 : Conditional Check
if(x && y) return mid;
If both 'x' and 'y' are true, the current element is a peak, so return the index 'mid'.
9 : Conditional Check
if(!x && y) r = mid -1;
If the current element is smaller than its left neighbor, move the right boundary 'r' to 'mid - 1' to search the left half.
10 : Conditional Check
elseif(x &&!y) l = mid +1;
If the current element is greater than its left neighbor but smaller than its right neighbor, move the left boundary 'l' to 'mid + 1' to search the right half.
11 : Conditional Check
else r = mid -1;
If neither of the above conditions is met, adjust the right boundary 'r' to search the left half.
12 : Return Statement
return l;
If no peak is found during the binary search, return the left boundary 'l', which will point to the index of the peak element.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: Each binary search step reduces the search space by half, resulting in O(log n) time complexity.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only use a few variables for indexing and comparisons.
