Array Peak Finder

Write a function findPeak that takes an array of integers and returns the index of any “peak” element. An element is considered a peak if it is greater than or equal to its neighbors. For elements at the boundaries of the array, consider only one neighbor.

Constraints:

The input array will contain at least one element.
The elements of the array are integers.

Example:

Input: [1, 3, 20, 4, 1, 0]
Output: 2
Explanation: The element at index 2 (which is 20) is a peak because it is greater than its neighbors (3 and 4).

Input: [5, 10, 20, 15]
Output: 2 or 3
Explanation: The elements at index 2 (20) and index 3 (15) are peaks. 20 is greater than both its neighbors and 15 is greater than its only neighbor (20).

Approach:

Iterate through the array.
Check if the current element is greater than or equal to its neighbors.
Return the index of the first element that satisfies this condition.

Tips:

Remember to handle edge cases where the peak element might be at the start or end of the array.

Solution

What’s the Exact Problem?

The problem is to find a “peak” element in an array of integers. A peak element is one that is greater than or equal to its neighbors. For the first and last elements, which have only one neighbor, the condition applies to that one neighbor.

Steps to Understand the Problem:

Recognize that a peak element is defined by its relation to its immediate neighbors in the array.
Understand that special consideration is needed for the first and last elements in the array.
The goal is to find the index of any one peak element in the array.

Examples:

Example 1: For the array [1, 3, 20, 4, 1, 0], the peak is at index 2 (element 20), as 20 is greater than both 3 and 4.
Example 2: In [5, 10, 20, 15], the peaks are at indices 2 and 3 (elements 20 and 15).

What Your Function Should Do:

The function findPeak should take an array of integers as input and return the index of a peak element. If multiple peaks exist, returning any one peak index is acceptable.

How to Solve the Problem:

Iterate through the array.
For each element, compare it with its neighbors.
If an element is found to be greater than or equal to its neighbors, return its index.
Pay special attention to the first and last elements, which have only one neighbor.

Code Solution

def findPeak(arr):
    n = len(arr)
    if n == 1:
        return 0
    if arr[0] >= arr[1]:
        return 0
    if arr[n - 1] >= arr[n - 2]:
        return n - 1
    for i in range(1, n - 1):
        if arr[i] >= arr[i - 1] and arr[i] >= arr[i + 1]:
            return i
    return -1

Example Usage

print(findPeak([1, 3, 20, 4, 1, 0]))  # Output could be 2
print(findPeak([5, 10, 20, 15]))       # Output could be 2 or 3

How this Code Works:

The code first handles special cases where the array size is 1 or where the peak is at the first or last element.
For other cases, it iterates through the array, starting from the second element and ending at the second-to-last element.
In each iteration, it checks if the current element is greater than or equal to both its left and right neighbors.
If such an element is found, its index is immediately returned.
The function ensures efficient checking of all elements and accurately finds a peak. If no peak is found (unlikely given the problem’s constraints), it returns -1 as a fallback.

Time Complexity: O(n)

The solution involves iterating through the array of integers.
In the worst case, the function checks each element once until it finds a peak or reaches the end of the array.
Since the iteration goes through the array linearly, the time complexity is proportional to the number of elements in the array.
Therefore, the time complexity is O(n), where n is the length of the input array.