NUHMAN.com

Introduction

LeetCode 162 asks us to find a peak element in a given array. A peak element is an element that is greater than or equal to its neighbors. For the edge elements of the array, we only consider one neighbor. The task is to find an index i such that nums[i] is a peak element.

Problem Statement

Given an integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index of any of the peaks.

Function Signature:

go

func findPeakElement(nums []int) int

• Input:
• A list of integers nums, where 1 <= len(nums) <= 1000 and -2^31 <= nums[i] <= 2^31 - 1.
• Output:
• The index i such that nums[i] is a peak element.

Approach

This problem can be solved using a binary search approach. Here's the reasoning:

1. Peak Definition: A peak element is greater than or equal to its neighbors. For edge elements (first or last element), only one neighbor is considered.
2. Binary Search Approach:

• We perform a binary search over the array and at each step, we check the middle element nums[mid].
• If nums[mid] is greater than both its neighbors, then it is a peak element, and we return its index.
• If the left neighbor is greater than nums[mid], then the peak must lie in the left half of the array (because there’s a larger value to the left). We move the search to the left half.
• If the right neighbor is greater than nums[mid], then the peak must lie in the right half of the array. We move the search to the right half.

1. Termination Condition: The binary search continues until we find a peak, which is guaranteed to exist in the array.

Time Complexity:

• O(log n) where n is the length of the array. This is because we reduce the search space by half in each step of the binary search.

Space Complexity:

• O(1) because we only use a constant amount of extra space.

Go Implementation

go

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    
    for left < right {
        mid := left + (right-left)/2
        
        // Compare mid with its right neighbor
        if nums[mid] > nums[mid+1] {
            // If mid is greater than its right neighbor, the peak is in the left half
            right = mid
        } else {
            // If mid is less than or equal to its right neighbor, the peak is in the right half
            left = mid + 1
        }
    }
    
    // At the end of the loop, left == right, which is the index of a peak element
    return left
}

Explanation of the Code:

1. Binary Search Setup:

• We initialize left to 0 and right to the last index of the array (len(nums)-1).

2. Iterative Binary Search:

• We calculate the middle index mid as left + (right-left)/2 to avoid overflow.
• We then check if the element at mid is greater than its right neighbor (nums[mid+1]). If it is, the peak lies in the left half of the array, so we move right to mid.
• If nums[mid] is less than or equal to nums[mid+1], the peak lies in the right half, so we move left to mid+1.

3. Termination:

• The loop continues until left == right. At this point, left (or right) points to a peak element, and we return the index left.

Example

Example 1:

go

nums := []int{1, 2, 3, 1}
result := findPeakElement(nums)
fmt.Println(result) // Output: 2

Explanation:

• nums[2] = 3 is greater than both its neighbors (2 and 1), so the peak element is at index 2.

Example 2:

go

nums := []int{1, 2, 1, 3, 5, 6, 4}
result := findPeakElement(nums)
fmt.Println(result) // Output: 5

Explanation:

• nums[5] = 6 is greater than both its neighbors (5 and 4), so the peak element is at index 5.

Example 3:

go

nums := []int{1, 2}
result := findPeakElement(nums)
fmt.Println(result) // Output: 1

Explanation:

• nums[1] = 2 is the peak element because it is greater than 1, and it is the last element in the array.

Example 4:

go

nums := []int{3, 2, 1}
result := findPeakElement(nums)
fmt.Println(result) // Output: 0

Explanation:

• nums[0] = 3 is the peak element because it is greater than 2, and it is the first element in the array.

Conclusion

LeetCode 162 provides a clear problem where binary search can be applied efficiently. By reducing the search space in half at each step, we are able to find a peak element in O(log n) time, which is much faster than a linear scan. The algorithm guarantees that there is at least one peak in any array of length 1 or greater.