Jobs

Interviews

Discussions

Valid Mountain Array

Easy

Google

3 views

Topics:

ArraysTwo Pointers

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 10⁴

Try coding it in LeetCode

Valid Mountain Array

Easy

Google

3 views

Topics:

ArraysTwo Pointers

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 10⁴

Try coding it in LeetCode

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 minimum length of the array? Is an array with length less than 3 considered a mountain array?
Can the input array contain non-integer values (e.g., floats)?
Can the values in the array be negative or zero?
If there are multiple peaks in the array, is it still considered a valid mountain array?
What should I return if the input array is null or empty?

Brute Force Solution

Approach

The brute force approach to identifying a mountain involves checking every possible place where the peak could be. We verify that the numbers increase until the potential peak, then decrease after the peak.

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

Assume that the first number is the peak and verify the criteria for a mountain.
If this doesn't match then assume the second number is the peak and again verify the criteria for a mountain.
Repeat this process for every number as a potential peak.
A valid mountain array will only be identified when one of the numbers as a peak satisfies the increasing before peak and decreasing after peak condition.

Code Implementation

def valid_mountain_array_brute_force(numbers):
    array_length = len(numbers)

    for potential_peak_index in range(array_length):
        # Peak cannot be the first or last element
        if potential_peak_index == 0 or potential_peak_index == array_length - 1:
            continue

        is_valid_mountain = True

        # Check increasing sequence before the peak
        for index_before_peak in range(potential_peak_index):
            if numbers[index_before_peak] >= numbers[index_before_peak + 1]:
                is_valid_mountain = False
                break

        # Check decreasing sequence after the peak
        if is_valid_mountain:
            for index_after_peak in range(potential_peak_index, array_length - 1):
                if numbers[index_after_peak] <= numbers[index_after_peak + 1]:
                    is_valid_mountain = False
                    break

        # We have found a valid peak
        if is_valid_mountain:
            return True

    # If no valid peak is found, return False
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the array of size n, assuming it to be the peak. For each potential peak, it iterates through the array again to verify if the elements increase before the peak and decrease after the peak. This nested iteration results in approximately n * n operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The described algorithm iterates through each element of the input array, considering it as a potential peak. However, it does not create any auxiliary data structures like lists, maps, or sets to store intermediate results or track visited elements. The space used is limited to a few variables for indexing and comparison, and this space remains constant regardless of the input array size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We want to check if a group of numbers looks like a mountain: first going up, then coming down. The key idea is to walk through the numbers and confirm that we first move upward to the peak, and then downward after reaching the peak. We can avoid unnecessary checks by stopping early if the 'mountain' shape is broken at any point.

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

Start at the beginning of the numbers.
Keep moving forward as long as each number is bigger than the one before it. This shows we are climbing the mountain.
If we reach the end while still climbing, or if we never even started climbing, it's not a mountain.
Remember the highest point we reached, which is the peak of the mountain.
Now, keep moving forward as long as each number is smaller than the one before it. This shows we are descending the mountain.
If we reach the end while still descending, and if we did both climb and descend at some point, then it is a valid mountain.

Code Implementation

def is_valid_mountain_array(arr): 
    array_length = len(arr)
    current_index = 0

    # Need at least three elements
    if array_length < 3:
        return False

    # Walk up the mountain
    while current_index + 1 < array_length and arr[current_index] < arr[current_index + 1]:
        current_index += 1

    # Peak can't be the first or last element
    if current_index == 0 or current_index == array_length - 1:
        return False

    # Walk down the mountain
    # Make sure we are actually descending now.
    while current_index + 1 < array_length and arr[current_index] > arr[current_index + 1]:
        current_index += 1

    # Check if we reached the end
    # It is a valid mountain if we reached the end.
    return current_index == array_length - 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n to find the peak and then iterates again to check the descent. In the worst-case scenario, we traverse the array twice, but these traversals are sequential, not nested. Therefore, the number of operations is proportional to the size of the input array n, making the time complexity O(n).

Space Complexity

O(1) – The algorithm iterates through the input array, keeping track of the current state (climbing or descending) and using index variables. No additional data structures like arrays, hash maps, or trees are created. The amount of extra memory needed remains constant regardless of the input array's size N, therefore the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately, as a mountain array must have at least 3 elements.
Array with only one or two elements	Return false immediately, as a mountain array must have at least 3 elements and both an increasing and decreasing section.
Array is strictly increasing or strictly decreasing	Return false, as a mountain array must have both increasing and decreasing portions.
Peak is the first or last element	Return false, as the peak cannot be the first or last element in a mountain array, since it needs increasing and decreasing portions before and after the peak, respectively.
Array contains duplicate values such that there is no clear peak	The algorithm should still identify whether there is an increasing followed by a decreasing sequence, and return false if it is not consistently trending as mountain range.
Array with large number of elements impacting performance	The linear time complexity O(n) of the one-pass or two-pass approach ensures it scales reasonably with large input sizes; no performance issues expected.
Integer overflow if calculating differences between elements for very large integer values	This algorithm does not perform arithmetic calculation which can lead to integer overflow issues between elements, as such, no overflow concerns exist here.
Array contains negative numbers or zeros	Negative numbers and zeros do not invalidate the mountain array property, so the algorithm handles them correctly as long as the increasing and decreasing sequences are valid.

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 minimum length of the array? Is an array with length less than 3 considered a mountain array?
Can the input array contain non-integer values (e.g., floats)?
Can the values in the array be negative or zero?
If there are multiple peaks in the array, is it still considered a valid mountain array?
What should I return if the input array is null or empty?

Brute Force Solution

Approach

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

Assume that the first number is the peak and verify the criteria for a mountain.
If this doesn't match then assume the second number is the peak and again verify the criteria for a mountain.
Repeat this process for every number as a potential peak.
A valid mountain array will only be identified when one of the numbers as a peak satisfies the increasing before peak and decreasing after peak condition.

Code Implementation

def valid_mountain_array_brute_force(numbers):
    array_length = len(numbers)

    for potential_peak_index in range(array_length):
        # Peak cannot be the first or last element
        if potential_peak_index == 0 or potential_peak_index == array_length - 1:
            continue

        is_valid_mountain = True

        # Check increasing sequence before the peak
        for index_before_peak in range(potential_peak_index):
            if numbers[index_before_peak] >= numbers[index_before_peak + 1]:
                is_valid_mountain = False
                break

        # Check decreasing sequence after the peak
        if is_valid_mountain:
            for index_after_peak in range(potential_peak_index, array_length - 1):
                if numbers[index_after_peak] <= numbers[index_after_peak + 1]:
                    is_valid_mountain = False
                    break

        # We have found a valid peak
        if is_valid_mountain:
            return True

    # If no valid peak is found, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the beginning of the numbers.
Keep moving forward as long as each number is bigger than the one before it. This shows we are climbing the mountain.
If we reach the end while still climbing, or if we never even started climbing, it's not a mountain.
Remember the highest point we reached, which is the peak of the mountain.
Now, keep moving forward as long as each number is smaller than the one before it. This shows we are descending the mountain.
If we reach the end while still descending, and if we did both climb and descend at some point, then it is a valid mountain.

Code Implementation

def is_valid_mountain_array(arr): 
    array_length = len(arr)
    current_index = 0

    # Need at least three elements
    if array_length < 3:
        return False

    # Walk up the mountain
    while current_index + 1 < array_length and arr[current_index] < arr[current_index + 1]:
        current_index += 1

    # Peak can't be the first or last element
    if current_index == 0 or current_index == array_length - 1:
        return False

    # Walk down the mountain
    # Make sure we are actually descending now.
    while current_index + 1 < array_length and arr[current_index] > arr[current_index + 1]:
        current_index += 1

    # Check if we reached the end
    # It is a valid mountain if we reached the end.
    return current_index == array_length - 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately, as a mountain array must have at least 3 elements.
Array with only one or two elements	Return false immediately, as a mountain array must have at least 3 elements and both an increasing and decreasing section.
Array is strictly increasing or strictly decreasing	Return false, as a mountain array must have both increasing and decreasing portions.
Peak is the first or last element	Return false, as the peak cannot be the first or last element in a mountain array, since it needs increasing and decreasing portions before and after the peak, respectively.
Array contains duplicate values such that there is no clear peak	The algorithm should still identify whether there is an increasing followed by a decreasing sequence, and return false if it is not consistently trending as mountain range.
Array with large number of elements impacting performance	The linear time complexity O(n) of the one-pass or two-pass approach ensures it scales reasonably with large input sizes; no performance issues expected.
Integer overflow if calculating differences between elements for very large integer values	This algorithm does not perform arithmetic calculation which can lead to integer overflow issues between elements, as such, no overflow concerns exist here.
Array contains negative numbers or zeros	Negative numbers and zeros do not invalidate the mountain array property, so the algorithm handles them correctly as long as the increasing and decreasing sequences are valid.