algoadvance

Leetcode 162. Find Peak Element

Problem Statement

A peak element is an element that is strictly greater than its neighbors. Given an integer 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] = -∞ and nums[n] = -∞ (where n is the length of the array).

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

Clarifying Questions

  1. Can the array contain negative numbers?
    • Yes, the range includes negative numbers.
  2. Do we need to return multiple indices if there are multiple peak elements?
    • No, only one peak index needs to be returned.
  3. Are the edge values considered their own neighborhood with -∞?
    • Yes, the array is bordered by virtual -∞.

Strategy

Given the requirement to achieve O(log n) time complexity, we can utilize a binary search approach. The idea is to:

  1. Use binary search on the array.
  2. Check the middle element and compare it with its neighbors.
  3. Based on the comparison, decide to move to the left or right half of the array:
    • If the middle element is greater than its right neighbor, then the peak lies on the left half (including the middle element).
    • Otherwise, the peak lies on the right half.

The process repeats until a peak is found.

Code

#include <vector>
#include <iostream>

int findPeakElement(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (int)((right - left) / 2); // to avoid potential overflow

        if (nums[mid] > nums[mid + 1]) {
            // Mid might be a peak, so search in [left, mid]
            right = mid;
        } else {
            // Peak must be in [mid + 1, right]
            left = mid + 1;
        }
    }

    // `left` should be pointing to the peak element at the end of the loop
    return left;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 1};
    std::cout << "Index of a peak element: " << findPeakElement(nums) << std::endl;

    std::vector<int> nums2 = {1, 2, 1, 3, 5, 6, 4};
    std::cout << "Index of a peak element: " << findPeakElement(nums2) << std::endl;

    return 0;
}

Time Complexity

The time complexity of this algorithm is O(log n) because each step of the binary search reduces the search space by half. This is efficient for large arrays and meets the problem requirements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI