Python Program to Find Peak Element in Array

A peak element in an array is an element that is greater than its neighbors. You can find it in Python using a simple loop: for i in range(len(arr)): if (i == 0 or arr[i] > arr[i-1]) and (i == len(arr)-1 or arr[i] > arr[i+1]): return arr[i].

Examples

Input[1, 3, 20, 4, 1, 0]

Output20

Input[10, 20, 15, 2, 23, 90, 67]

Output20

Input[5]

Output5

How to Think About It

To find a peak element, check each element and compare it with its neighbors. If it is greater than the element before it and the element after it, it is a peak. For the first and last elements, only one neighbor exists, so compare with that one only.

Algorithm

1

Get the input array.

2

Loop through each element in the array.

3

For each element, check if it is greater than its left neighbor (or if it is the first element).

4

Also check if it is greater than its right neighbor (or if it is the last element).

5

If both conditions are true, return this element as the peak.

6

If no peak is found in the loop, return None.

Code

python

def find_peak(arr):
    n = len(arr)
    for i in range(n):
        if (i == 0 or arr[i] > arr[i-1]) and (i == n-1 or arr[i] > arr[i+1]):
            return arr[i]
    return None

# Example usage
arr = [1, 3, 20, 4, 1, 0]
print(find_peak(arr))

Output

20

Dry Run

Let's trace the array [1, 3, 20, 4, 1, 0] through the code to find the peak element.

1

Check element at index 0

arr[0] = 1, left neighbor does not exist, right neighbor = 3; 1 > 3? No, so not peak.

2

Check element at index 1

arr[1] = 3, left neighbor = 1, right neighbor = 20; 3 > 1? Yes, 3 > 20? No, so not peak.

3

Check element at index 2

arr[2] = 20, left neighbor = 3, right neighbor = 4; 20 > 3? Yes, 20 > 4? Yes, so peak found.

Index	Element	Left Neighbor	Right Neighbor	Is Peak?
0	1	None	3	No
1	3	1	20	No
2	20	3	4	Yes

Why This Works

Step 1: Check neighbors

The code compares each element with its neighbors using arr[i] > arr[i-1] and arr[i] > arr[i+1] to find if it is a peak.

Step 2: Handle edges

For the first and last elements, the code only compares with the one neighbor they have by checking i == 0 or i == n-1.

Step 3: Return peak

Once a peak is found, the function returns it immediately, ensuring the first peak is returned quickly.

Alternative Approaches

Binary Search Approach

python

def find_peak_binary(arr):
    low, high = 0, len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < arr[mid + 1]:
            low = mid + 1
        else:
            high = mid
    return arr[low]

print(find_peak_binary([1, 3, 20, 4, 1, 0]))

This method is faster (O(log n)) but more complex to understand than the simple loop.

Using max with condition

python

def find_peak_simple(arr):
    for i in range(len(arr)):
        left = arr[i-1] if i > 0 else float('-inf')
        right = arr[i+1] if i < len(arr)-1 else float('-inf')
        if arr[i] > left and arr[i] > right:
            return arr[i]
    return None

print(find_peak_simple([1, 3, 20, 4, 1, 0]))

This is similar to the main method but uses negative infinity for edges to simplify comparisons.

Complexity: O(n) time, O(1) space

Time Complexity

The simple loop checks each element once, so it takes linear time O(n). The binary search alternative takes O(log n) time.

Space Complexity

The solution uses only a few variables and no extra space proportional to input size, so space is O(1).

Which Approach is Fastest?

Binary search is fastest for large arrays but more complex. The simple loop is easier to understand and fine for small to medium arrays.

Approach	Time	Space	Best For
Simple Loop	O(n)	O(1)	Small to medium arrays, easy to understand
Binary Search	O(log n)	O(1)	Large arrays, performance critical
Max with Condition	O(n)	O(1)	Readable code with clear edge handling