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] = -∞ (an element outside of the array is treated as negative infinity).

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.

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

Constraints:

Clarifying Questions:

  1. Can the input array contain only one element?
    • Yes, and in that case, that single element is the peak element.
  2. Are we allowed to modify the input array?
    • No, we should not modify the input array.
  3. What should be returned if there are multiple peak elements?
    • Return the index of any one of the peak elements.

Strategy:

Since the problem requires finding a peak element in O(log n) time, a binary search approach is suitable. Here’s how we can do it:

  1. Initialize two pointers, left and right, at the start and end of the array, respectively.
  2. While left is less than right, calculate the middle index mid = (left + right) / 2.
  3. Compare the middle element with its next element:
    • If nums[mid] < nums[mid + 1], it means the peak lies to the right of mid, so set left = mid + 1.
    • Otherwise, the peak lies to the left of mid or it is mid itself, so set right = mid.
  4. After the loop ends, left and right will converge to the peak element, return left (or right, they will be the same).

Code:

public class FindPeakElement {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2; // To avoid potential overflow
            
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }

    public static void main(String[] args) {
        FindPeakElement solution = new FindPeakElement();
        
        int[] nums1 = {1, 2, 3, 1};
        System.out.println(solution.findPeakElement(nums1)); // Output: 2
        
        int[] nums2 = {1, 2, 1, 3, 5, 6, 4};
        System.out.println(solution.findPeakElement(nums2)); // Output: 5 (or 1)
        
        int[] nums3 = {1};
        System.out.println(solution.findPeakElement(nums3)); // Output: 0
        
        int[] nums4 = {1, 2, 3, 4};
        System.out.println(solution.findPeakElement(nums4)); // Output: 3
    }
}

Time Complexity:

The algorithm runs in O(log n) time because we are effectively halving the search space in each iteration of the while loop. The space complexity is O(1) since no additional space proportional to the input size is used.

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