Jobs

Interviews

Discussions

Find Peak Element

Medium

Walmart

0 views

Topics:

ArraysBinary Search

A peak element is an element that is strictly greater than its neighbors.

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

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Find Peak Element

Medium

Walmart

0 views

Topics:

ArraysBinary Search

A peak element is an element that is strictly greater than its neighbors.

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

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the `nums` array? Should I be concerned about potential integer overflow issues?
Can the input array be empty or null? If so, what should I return?
If multiple peak elements exist, is there a preference as to which index I should return? For example, should I return the leftmost or rightmost peak?
Are the elements in the array guaranteed to be distinct? If not, how do I handle consecutive equal elements that may or may not be adjacent to a peak?
Given the constraint of O(log n) runtime, is it safe to assume the input array is large enough that a binary search approach will provide a significant performance improvement over a linear scan?

Brute Force Solution

Approach

The brute force approach to finding a peak involves examining each number in the list one by one. For each number, we check if it is larger than its neighbors. If it is, we've found a peak.

Here's how the algorithm would work step-by-step:

Look at the first number in the list.
Check if this number is bigger than the number next to it.
If it is, then this first number is a peak and we are done.
If it is not, move on to the second number in the list.
Check if this number is bigger than both the number before it and the number after it.
If it is, then this second number is a peak and we are done.
Keep doing this for every number in the list until you reach the last number.
For the last number, check if it is bigger than the number before it.
If it is, then this last number is a peak and we are done.
If you went through the entire list and found no peak, then something is wrong (or all the numbers are the same).

Code Implementation

def find_peak_element_brute_force(numbers):
    list_length = len(numbers)

    # Handle edge case of single element list
    if list_length == 1:
        return 0

    # Check if the first element is a peak
    if numbers[0] > numbers[1]:
        return 0

    # Iterate through the middle elements
    for index in range(1, list_length - 1):

        # Check if current element is greater than its neighbors
        if numbers[index] > numbers[index - 1] and numbers[index] > numbers[index + 1]:

            return index

    # Check if the last element is a peak
    if numbers[list_length - 1] > numbers[list_length - 2]:

        return list_length - 1

    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array 'nums' of size 'n' at most once. For each element, it performs a constant number of comparisons with its neighbors (at most two comparisons). Thus, the number of operations grows linearly with the size of the input array. The total operations can be approximated by a constant times n, which simplifies to O(n).

Space Complexity

O(1) – The provided brute-force algorithm iterates through the input list and compares elements. It does not create any auxiliary data structures like lists, dictionaries, or sets to store intermediate results. The algorithm only uses a few constant space variables to track the current element and its neighbors during comparisons. Therefore, the space complexity is independent of the input size N and remains constant. The auxiliary space used is O(1).

Optimal Solution

Approach

The goal is to find a 'high point' in a collection of numbers without checking every single number. We can use a clever strategy that quickly narrows down where that high point must be by repeatedly cutting the problem in half.

Here's how the algorithm would work step-by-step:

Start by looking at the middle number in the collection.
Compare the middle number to its immediate neighbors (the numbers right before and right after).
If the middle number is bigger than both of its neighbors, you've found a peak!
If the middle number is smaller than the number before it, then a peak must exist somewhere in the first half of the collection, so focus on only that half.
If the middle number is smaller than the number after it, then a peak must exist somewhere in the second half of the collection, so focus on only that half.
Repeat the process of looking at the middle number of the remaining section and comparing it to its neighbors, until you isolate a peak.

Code Implementation

def find_peak_element(nums):
    left_index = 0
    right_index = len(nums) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if middle element is greater than its right neighbor.
        if nums[middle_index] > nums[middle_index + 1]:

            right_index = middle_index

            # A peak must exist in the left half

        else:

            left_index = middle_index + 1

            # A peak must exist in the right half.

    return left_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs a binary search approach. With each step, the search space is halved. We start with an input array of size n, and in each iteration, we reduce the problem size by half, checking only the middle element and its neighbors. This halving continues until we find a peak element. The number of iterations required to reduce the problem to a constant size is logarithmic with base 2, therefore the time complexity is O(log n).

Space Complexity

O(log N) – The algorithm employs a binary search approach, repeatedly halving the search space. This halving is achieved through recursive calls (or an iterative equivalent using a stack). Each recursive call adds a new frame to the call stack, storing local variables like the middle index. In the worst-case scenario, the recursion depth (or stack size) is proportional to the number of times N can be divided by 2 before reaching 1, which is log2(N). Therefore, the space used by the recursion stack grows logarithmically with the input size N, resulting in O(log N) space complexity.

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 or throw an exception indicating no peak can be found as an empty array has no peak.
Array with a single element	Return index 0, as a single element is always a peak.
Array with two elements where the first is larger	Return index 0 as the first element is the peak.
Array with two elements where the second is larger	Return index 1 as the second element is the peak.
Array with elements in strictly increasing order	Return the index of the last element (n-1), as it's a peak according to the implied -infinity boundary.
Array with elements in strictly decreasing order	Return the index of the first element (0), as it's a peak according to the implied -infinity boundary.
Array with multiple peak elements	Binary search will naturally converge on one of the peaks, any peak is a valid solution.
Integer overflow when calculating mid = (left + right) / 2	Calculate mid as left + (right - left) / 2 to prevent overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the `nums` array? Should I be concerned about potential integer overflow issues?
Can the input array be empty or null? If so, what should I return?
If multiple peak elements exist, is there a preference as to which index I should return? For example, should I return the leftmost or rightmost peak?
Are the elements in the array guaranteed to be distinct? If not, how do I handle consecutive equal elements that may or may not be adjacent to a peak?
Given the constraint of O(log n) runtime, is it safe to assume the input array is large enough that a binary search approach will provide a significant performance improvement over a linear scan?

Brute Force Solution

Approach

The brute force approach to finding a peak involves examining each number in the list one by one. For each number, we check if it is larger than its neighbors. If it is, we've found a peak.

Here's how the algorithm would work step-by-step:

Look at the first number in the list.
Check if this number is bigger than the number next to it.
If it is, then this first number is a peak and we are done.
If it is not, move on to the second number in the list.
Check if this number is bigger than both the number before it and the number after it.
If it is, then this second number is a peak and we are done.
Keep doing this for every number in the list until you reach the last number.
For the last number, check if it is bigger than the number before it.
If it is, then this last number is a peak and we are done.
If you went through the entire list and found no peak, then something is wrong (or all the numbers are the same).

Code Implementation

def find_peak_element_brute_force(numbers):
    list_length = len(numbers)

    # Handle edge case of single element list
    if list_length == 1:
        return 0

    # Check if the first element is a peak
    if numbers[0] > numbers[1]:
        return 0

    # Iterate through the middle elements
    for index in range(1, list_length - 1):

        # Check if current element is greater than its neighbors
        if numbers[index] > numbers[index - 1] and numbers[index] > numbers[index + 1]:

            return index

    # Check if the last element is a peak
    if numbers[list_length - 1] > numbers[list_length - 2]:

        return list_length - 1

    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the middle number in the collection.
Compare the middle number to its immediate neighbors (the numbers right before and right after).
If the middle number is bigger than both of its neighbors, you've found a peak!
If the middle number is smaller than the number before it, then a peak must exist somewhere in the first half of the collection, so focus on only that half.
If the middle number is smaller than the number after it, then a peak must exist somewhere in the second half of the collection, so focus on only that half.
Repeat the process of looking at the middle number of the remaining section and comparing it to its neighbors, until you isolate a peak.

Code Implementation

def find_peak_element(nums):
    left_index = 0
    right_index = len(nums) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if middle element is greater than its right neighbor.
        if nums[middle_index] > nums[middle_index + 1]:

            right_index = middle_index

            # A peak must exist in the left half

        else:

            left_index = middle_index + 1

            # A peak must exist in the right half.

    return left_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 or throw an exception indicating no peak can be found as an empty array has no peak.
Array with a single element	Return index 0, as a single element is always a peak.
Array with two elements where the first is larger	Return index 0 as the first element is the peak.
Array with two elements where the second is larger	Return index 1 as the second element is the peak.
Array with elements in strictly increasing order	Return the index of the last element (n-1), as it's a peak according to the implied -infinity boundary.
Array with elements in strictly decreasing order	Return the index of the first element (0), as it's a peak according to the implied -infinity boundary.
Array with multiple peak elements	Binary search will naturally converge on one of the peaks, any peak is a valid solution.
Integer overflow when calculating mid = (left + right) / 2	Calculate mid as left + (right - left) / 2 to prevent overflow.