Summary of "BS-9. Find Peak Element"

Summary of “BS-9. Find Peak Element” Video

This video is part of a binary search playlist focused on solving the “Find Peak Element” problem using efficient algorithms. The instructor explains the problem, provides examples, discusses brute force and optimized solutions, and walks through the binary search approach with detailed reasoning and code logic.

Main Ideas and Concepts

Problem Definition

A peak element in an array is an element that is strictly greater than its neighbors (both left and right).
Edge elements are compared against a hypothetical value of minus infinity on their missing side.
The array may have one or multiple peaks.
The task is to find any one peak element (returning either the index or the element itself is acceptable).

Examples to Understand the Problem

Strictly increasing array ending with a peak.
Array with multiple peaks.
Strictly increasing or strictly decreasing arrays where the peak is at an end.
Visualization of the problem using graphs of increasing and decreasing sequences.

Brute Force Solution

Linear scan from left to right.
For each element, check if it is greater than its neighbors.
Time complexity: O(n)
Space complexity: O(1)
Not optimal and likely to be rejected in interviews.

Motivation for Binary Search

Need for a faster solution than O(n).
Binary search is suitable because the array exhibits a “sorted tendency” — parts of it are increasing or decreasing.
The problem can be reframed as searching for a peak in a partially sorted array.

Binary Search Approach (Single Peak Assumption)

Key Insight

If the middle element is less than its right neighbor, the peak lies on the right side.
If the middle element is less than its left neighbor, the peak lies on the left side.
If the middle element is greater than both neighbors, it is a peak.

Algorithm Steps

Initialize low = 0, high = n - 1.
Check if the first or last element is a peak (handle edge cases upfront).
While low <= high:
- Compute mid = (low + high) // 2.
- If arr[mid] is greater than neighbors, return mid.
- Else if arr[mid] < arr[mid + 1], move low to mid + 1.
- Else move high to mid - 1.

Handling Edge Cases

Check first and last elements separately before binary search to avoid index out-of-bound errors.
Shrink search space to between indices 1 and n-2 to simplify neighbor checks.

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Extending to Multiple Peaks

The binary search logic still works with multiple peaks due to the properties of the array:
- The array can be seen as alternating increasing and decreasing sequences.
- When discarding half the search space, at least one peak remains in the other half.
- The binary search will eventually narrow down to a subarray with a single peak.

Additional Considerations

There may be cases where the mid element is neither on a clear increasing nor decreasing slope (like a “valley”).
In such cases, moving either left or right still guarantees finding a peak.
The code can be simplified by using an else clause to move to either side if the main conditions fail.

Code Outline (Pseudocode)

function findPeakElement(arr):
    n = len(arr)

    # Handle single element array
    if n == 1:
        return 0

    # Check edges
    if arr[0] > arr[1]:
        return 0
    if arr[n-1] > arr[n-2]:
        return n-1

    low, high = 1, n - 2

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
            return mid
        elif arr[mid] < arr[mid+1]:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # This line is never reached due to problem constraints

Important Lessons

Visualizing the problem using graphs of increasing and decreasing sequences helps understand binary search applicability.
Handling edge cases upfront simplifies the binary search logic.
Binary search can be adapted to problems beyond strictly sorted arrays by leveraging problem-specific properties.
The approach works for arrays with multiple peaks with minimal modification.
Writing clean code with clear checks for boundaries is crucial to avoid errors.

Speakers / Sources

Primary Speaker: The instructor (likely Striver, given references to “Striver’s 80 Seconds” and “Strivoceto’s DSA course”)
No other speakers or external sources explicitly mentioned.

Summary

The video thoroughly explains the “Find Peak Element” problem, starting from the problem statement and examples, moving through brute force and optimized binary search solutions, and finally extending the binary search approach to arrays with multiple peaks. The instructor emphasizes visualization and handling edge cases to implement an efficient O(log n) solution suitable for interviews.