LeetCode 162: Find Peak Element Solution in Python Explained

Problem Statement

In LeetCode 162, you’re given an integer array nums. A peak element is one strictly greater than its neighbors (nums[i-1] < nums[i] > nums[i+1]), and your task is to return the index of any such element in O(log n) time. The array may contain multiple peaks, and edge elements compare only to their single neighbor. This differs from string comparison like LeetCode 161: One Edit Distance, focusing on array peak detection rather than edit operations.

Constraints

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• Adjacent elements are distinct (nums[i] != nums[i+1])
• O(log n) time complexity required

Example

Let’s see some cases:

Copy codeInput: nums = [1,2,3,1]
Output: 2
Explanation: nums[2] = 3 is a peak (2 < 3 > 1).

Copy codeInput: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: nums[1] = 2 (1 < 2 > 1) or nums[5] = 6 (5 < 6 > 4) are peaks.

Copy codeInput: nums = [1]
Output: 0
Explanation: Single element is a peak (no neighbors).

These examples show we’re finding a peak index.

Understanding the Problem

How do you solve LeetCode 162: Find Peak Element in Python? Take nums = [1,2,3,1]. We need an index where the element is greater than its neighbors—index 2 (value 3) works since 2 < 3 > 1. For [1,2,1,3,5,6,4], multiple peaks exist (e.g., 2 at 1, 6 at 5); we return any one. The O(log n) requirement suggests binary search, leveraging the fact that a peak must exist (due to distinct neighbors and finite length). This isn’t a list intersection task like LeetCode 160: Intersection of Two Linked Lists; it’s about array peak finding. We’ll use: 1. Binary Search: O(log n) time, O(1) space—our best solution. 2. Linear Search: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Binary Search Approach

Explanation

Binary Search finds a peak by leveraging the array’s property that a peak must exist and comparing adjacent elements:

• Use two pointers (left, right) to define the search range.
• Compute the middle element.
• Compare nums[mid] with nums[mid+1]:
• If nums[mid] < nums[mid+1], a peak must be in the right half (ascending slope).
• If nums[mid] > nums[mid+1], a peak must be in the left half or at mid (descending slope).
• Narrow the range until a peak is found.

This is the best solution due to its O(log n) time complexity, O(1) space usage, and efficient use of the array’s structure, meeting the problem’s performance goal perfectly.

For [1,2,3,1]:

• Mid=2 > 1, search left.
• Mid=2, peak at 2.

Step-by-Step Example

Example 1: nums = [1,2,3,1]

Goal: Return 2.

• Start: left = 0, right = 3.
• Step 1: mid = 1, nums[mid] = 2, nums[mid+1] = 3.
• 2 < 3, left = 2.
• Step 2: left = 2, right = 3, mid = 2, nums[mid] = 3, nums[mid+1] = 1.
• 3 > 1, right = 2.
• Step 3: left = 2, right = 2, return mid = 2.
• Finish: Return 2.

Example 2: nums = [1,2,1,3,5,6,4]

Goal: Return 1 or 5 (e.g., 5).

• Start: left = 0, right = 6.
• Step 1: mid = 3, nums[mid] = 3, nums[mid+1] = 5.
• 3 < 5, left = 4.
• Step 2: left = 4, right = 6, mid = 5, nums[mid] = 6, nums[mid+1] = 4.
• 6 > 4, right = 5.
• Step 3: left = 5, right = 5, return mid = 5.
• Finish: Return 5.

Example 3: nums = [1]

Goal: Return 0.

• Start: left = 0, right = 0, left == right.
• Finish: Return 0.

How the Code Works (Binary Search) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef findPeakElement(nums: list[int]) -> int:
    # Line 1: Initialize pointers
    left = 0
    # Left boundary (e.g., 0)
    right = len(nums) - 1
    # Right boundary (e.g., 3 for [1,2,3,1])

    # Line 2: Binary search loop
    while left < right:
        # Continue while range exists (e.g., 0 < 3)

        # Line 3: Calculate mid point
        mid = left + (right - left) // 2
        # Avoid overflow (e.g., 0+(3-0)//2=1)

        # Line 4: Compare mid with next element
        if nums[mid] < nums[mid + 1]:
            # If mid < next (e.g., 2 < 3), peak in right half
            left = mid + 1
            # Move left (e.g., 2)
        else:
            # If mid > next (e.g., 3 > 1), peak in left half or at mid
            right = mid
            # Move right (e.g., 2)

    # Line 5: Return peak index
    return left
    # Left points to peak (e.g., 2)

This detailed breakdown clarifies how binary search efficiently finds a peak element.

Alternative: Linear Search Approach

Explanation

Linear Search scans the array sequentially, checking each element against its neighbors:

• For index 0, check nums[0] > nums[1].
• For index n-1, check nums[n-1] > nums[n-2].
• For others, check nums[i-1] < nums[i] > nums[i+1].
• Return the first peak found.

It’s a practical alternative, simple with O(n) time, but doesn’t meet the O(log n) requirement, using O(1) space.

For [1,2,3,1]:

• 1 < 2, 2 < 3, 3 > 1, return 2.

Step-by-Step Example (Alternative)

For [1,2,1,3,5,6,4]:

• Step 1: i=0, 1 < 2, continue.
• Step 2: i=1, 1 < 2 > 1, return 1.
• Finish: Return 1.

How the Code Works (Linear Search)

Copy codedef findPeakElementLinear(nums: list[int]) -> int:
    if len(nums) == 1:
        return 0
    for i in range(len(nums)):
        if i == 0:
            if nums[i] > nums[i+1]:
                return i
        elif i == len(nums) - 1:
            if nums[i] > nums[i-1]:
                return i
        else:
            if nums[i-1] < nums[i] > nums[i+1]:
                return i
    return 0

Complexity

• Binary Search:
• Time: O(log n) – halves search space.
• Space: O(1) – constant space.
• Linear Search:
• Time: O(n) – single pass.
• Space: O(1) – constant space.

Efficiency Notes

Binary Search is the best solution with O(log n) time and O(1) space, meeting the problem’s efficiency goal—Linear Search uses O(n) time, making it simpler but slower, though space-efficient.

Key Insights

• Peak: Greater than neighbors.
• Binary: Exploits slope direction.
• Linear: Checks all elements.

Additional Example

For nums = [3,2,1]:

• Goal: 0.
• Binary: Mid=2 < 1, left=0, peak at 0.

Edge Cases

• Single Element: [1] → 0.
• Monotonic: [1,2,3] → 2.
• Reverse: [3,2,1] → 0.

Both solutions handle these well.

Final Thoughts

LeetCode 162: Find Peak Element in Python is a smart array challenge. The Binary Search solution excels with its efficiency and elegance, while Linear Search offers a straightforward approach. Want more? Try LeetCode 153: Find Minimum in Rotated Sorted Array for binary search practice or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 162 on LeetCode with [1,2,3,1], aiming for 2—test your skills now!