Jobs

Interviews

Discussions

Longest Mountain in Array

Medium

Databricks

1 view

Topics:

ArraysTwo Pointers

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) 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]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

Constraints:

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

Follow up:

Can you solve it using only one pass?
Can you solve it in O(1) space?

Try coding it in LeetCode

Longest Mountain in Array

Medium

Databricks

1 view

Topics:

ArraysTwo Pointers

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) 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]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

Constraints:

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

Follow up:

Can you solve it using only one pass?
Can you solve it in O(1) space?

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 are the constraints on the size of the input array 'arr'?
Can the input array contain negative integers, zero, or only positive integers?
If the input array does not contain any mountain, what value should I return?
Can there be plateaus in the 'mountain', i.e., can consecutive elements be equal?
Could you clarify the expected behavior if there are multiple mountains of the same maximum length? Should I return the length of any one of them?

Brute Force Solution

Approach

The brute force strategy to find the longest mountain involves examining every possible section of the numbers to see if it forms a mountain. We check each section to see if it first goes up and then goes down. We then record the length of valid mountains and pick the longest one.

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

Consider every possible group of numbers within the given numbers.
For each group, check if it meets the definition of a mountain: increasing first, then decreasing.
If the group is a mountain, determine its length.
Compare the length of the current mountain with the length of the longest mountain seen so far.
If the current mountain is longer, remember its length.
After checking every group, return the length of the longest mountain found.

Code Implementation

def longest_mountain_in_array_brute_force(numbers):
    longest_mountain_length = 0
    array_length = len(numbers)

    for start_index in range(array_length):
        for end_index in range(start_index + 2, array_length + 1):
            sub_array = numbers[start_index:end_index]
            sub_array_length = len(sub_array)

            is_mountain = False
            peak_index = -1

            # Find the peak, if any. The peak is essential to be a mountain
            for index in range(1, sub_array_length - 1):
                if sub_array[index] > sub_array[index - 1] and sub_array[index] > sub_array[index + 1]:
                    peak_index = index
                    break

            if peak_index != -1:
                is_increasing = True
                for index in range(1, peak_index + 1):
                    if sub_array[index] <= sub_array[index - 1]:
                        is_increasing = False
                        break

                is_decreasing = True
                for index in range(peak_index + 1, sub_array_length):
                    if sub_array[index] >= sub_array[index - 1]:
                        is_decreasing = False
                        break

                # Confirm both halves increase and decrease.
                if is_increasing and is_decreasing:
                    is_mountain = True

            if is_mountain:
                longest_mountain_length = max(longest_mountain_length, sub_array_length)

    return longest_mountain_length

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible subarrays of the input array of size n. This involves a nested loop structure to define the start and end indices of each subarray, resulting in O(n²) iterations. For each subarray, the algorithm checks if it forms a valid mountain, which requires iterating through the elements of the subarray to verify the increasing and decreasing pattern, taking O(n) time in the worst case. Therefore, the overall time complexity is O(n²) * O(n) = O(n³).

Space Complexity

O(1) – The described brute force approach only uses a few constant space variables such as the current mountain's length and the longest mountain seen so far. It iterates through subarrays using indices, and these indices occupy constant space. No auxiliary data structures like arrays or hash maps are created to store intermediate results. Therefore, the space complexity is independent of the input size N and is constant.

Optimal Solution

Approach

The goal is to find the longest 'mountain' shape within a series of numbers. Instead of checking every possible range, the trick is to efficiently build mountain slopes from each point, extending them as far as possible and only when a peak is found, compare it against our result.

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

Go through the numbers one by one.
For each number, try to build an increasing slope to the left as far as possible.
Then, try to build a decreasing slope to the right as far as possible.
If both increasing and decreasing slopes exist around the number, it's a peak of a mountain.
Calculate the length of this mountain (increasing slope + decreasing slope + the peak number itself).
Keep track of the longest mountain found so far, updating it if a longer one is discovered.
By extending slopes outwards from each potential peak, you explore mountain lengths effectively without unnecessary recalculations.

Code Implementation

def longest_mountain(array):
    array_length = len(array)
    longest_mountain_length = 0

    for i in range(1, array_length - 1):
        # Check if current element is a peak
        if array[i - 1] < array[i] and array[i] > array[i + 1]:

            left_index = i - 1
            # Expand left while increasing
            while left_index > 0 and array[left_index - 1] < array[left_index]:
                left_index -= 1

            right_index = i + 1
            # Expand right while decreasing
            while right_index < array_length - 1 and array[right_index] > array[right_index + 1]:
                right_index += 1

            # Calculate mountain length
            mountain_length = right_index - left_index + 1

            # Update longest mountain length
            longest_mountain_length = max(longest_mountain_length, mountain_length)

    return longest_mountain_length

Big(O) Analysis

Time Complexity

O(n) – We iterate through the array of n elements once. For each element, we extend increasing slopes to the left and decreasing slopes to the right. Although there are while loops inside the for loop, each element is visited and considered for expansion only a constant number of times, because when we find a valid mountain from some index we update i (the current index of the main loop) to jump to the end of the mountain we just processed, skipping elements that are already part of a mountain. Therefore, each element is visited at most a few times, leading to a linear time complexity. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the input array, calculating increasing and decreasing slopes from each point, but it doesn't store these slopes explicitly in any auxiliary data structure. It only keeps track of the current mountain length and the longest mountain found so far using a few variables. Therefore, the space used is independent of the input array's size (N). The auxiliary space remains constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty array or null input	Return 0 as there can be no mountain in an empty array or null input.
Array with fewer than 3 elements	Return 0 as a mountain requires at least 3 elements (increasing, peak, decreasing).
Array with all elements identical	Return 0 as a mountain requires strictly increasing and decreasing sequences.
Array is strictly increasing	Return 0 as there is no decreasing portion of the mountain.
Array is strictly decreasing	Return 0 as there is no increasing portion of the mountain.
Array contains only a single peak element surrounded by smaller elements	This is a valid mountain, and the algorithm should correctly calculate its length.
Array contains multiple mountains, possibly overlapping	The algorithm should find the longest mountain, even if others exist.
Array contains integers near the maximum or minimum integer values to prevent integer overflow in length calculations	Use appropriate data types (e.g., long) or careful comparisons to avoid integer 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 are the constraints on the size of the input array 'arr'?
Can the input array contain negative integers, zero, or only positive integers?
If the input array does not contain any mountain, what value should I return?
Can there be plateaus in the 'mountain', i.e., can consecutive elements be equal?
Could you clarify the expected behavior if there are multiple mountains of the same maximum length? Should I return the length of any one of them?

Brute Force Solution

Approach

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

Consider every possible group of numbers within the given numbers.
For each group, check if it meets the definition of a mountain: increasing first, then decreasing.
If the group is a mountain, determine its length.
Compare the length of the current mountain with the length of the longest mountain seen so far.
If the current mountain is longer, remember its length.
After checking every group, return the length of the longest mountain found.

Code Implementation

def longest_mountain_in_array_brute_force(numbers):
    longest_mountain_length = 0
    array_length = len(numbers)

    for start_index in range(array_length):
        for end_index in range(start_index + 2, array_length + 1):
            sub_array = numbers[start_index:end_index]
            sub_array_length = len(sub_array)

            is_mountain = False
            peak_index = -1

            # Find the peak, if any. The peak is essential to be a mountain
            for index in range(1, sub_array_length - 1):
                if sub_array[index] > sub_array[index - 1] and sub_array[index] > sub_array[index + 1]:
                    peak_index = index
                    break

            if peak_index != -1:
                is_increasing = True
                for index in range(1, peak_index + 1):
                    if sub_array[index] <= sub_array[index - 1]:
                        is_increasing = False
                        break

                is_decreasing = True
                for index in range(peak_index + 1, sub_array_length):
                    if sub_array[index] >= sub_array[index - 1]:
                        is_decreasing = False
                        break

                # Confirm both halves increase and decrease.
                if is_increasing and is_decreasing:
                    is_mountain = True

            if is_mountain:
                longest_mountain_length = max(longest_mountain_length, sub_array_length)

    return longest_mountain_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the numbers one by one.
For each number, try to build an increasing slope to the left as far as possible.
Then, try to build a decreasing slope to the right as far as possible.
If both increasing and decreasing slopes exist around the number, it's a peak of a mountain.
Calculate the length of this mountain (increasing slope + decreasing slope + the peak number itself).
Keep track of the longest mountain found so far, updating it if a longer one is discovered.
By extending slopes outwards from each potential peak, you explore mountain lengths effectively without unnecessary recalculations.

Code Implementation

def longest_mountain(array):
    array_length = len(array)
    longest_mountain_length = 0

    for i in range(1, array_length - 1):
        # Check if current element is a peak
        if array[i - 1] < array[i] and array[i] > array[i + 1]:

            left_index = i - 1
            # Expand left while increasing
            while left_index > 0 and array[left_index - 1] < array[left_index]:
                left_index -= 1

            right_index = i + 1
            # Expand right while decreasing
            while right_index < array_length - 1 and array[right_index] > array[right_index + 1]:
                right_index += 1

            # Calculate mountain length
            mountain_length = right_index - left_index + 1

            # Update longest mountain length
            longest_mountain_length = max(longest_mountain_length, mountain_length)

    return longest_mountain_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or null input	Return 0 as there can be no mountain in an empty array or null input.
Array with fewer than 3 elements	Return 0 as a mountain requires at least 3 elements (increasing, peak, decreasing).
Array with all elements identical	Return 0 as a mountain requires strictly increasing and decreasing sequences.
Array is strictly increasing	Return 0 as there is no decreasing portion of the mountain.
Array is strictly decreasing	Return 0 as there is no increasing portion of the mountain.
Array contains only a single peak element surrounded by smaller elements	This is a valid mountain, and the algorithm should correctly calculate its length.
Array contains multiple mountains, possibly overlapping	The algorithm should find the longest mountain, even if others exist.
Array contains integers near the maximum or minimum integer values to prevent integer overflow in length calculations	Use appropriate data types (e.g., long) or careful comparisons to avoid integer overflow.