Jobs

Interviews

Discussions

Find Indices of Stable Mountains

#329 Most AskedEasy

Find Indices of Stable Mountains #329 Most Asked

Easy

Google

8 views

Topics:

Arrays

There are n mountains in a row, and each mountain has a height. You are given an integer array height where height[i] represents the height of mountain i, and an integer threshold.

A mountain is called stable if the mountain just before it (if it exists) has a height strictly greater than threshold. Note that mountain 0 is not stable.

Return an array containing the indices of all stable mountains in any order.

Example 1:

Input: height = [1,2,3,4,5], threshold = 2

Output: [3,4]

Explanation:

Mountain 3 is stable because height[2] == 3 is greater than threshold == 2.
Mountain 4 is stable because height[3] == 4 is greater than threshold == 2.

Example 2:

Input: height = [10,1,10,1,10], threshold = 3

Output: [1,3]

Example 3:

Input: height = [10,1,10,1,10], threshold = 10

Output: []

Constraints:

2 <= n == height.length <= 100
1 <= height[i] <= 100
1 <= threshold <= 100

Try coding it in LeetCode

Find Indices of Stable Mountains

#329 Most AskedEasy

Find Indices of Stable Mountains #329 Most Asked

Easy

Google

8 views

Topics:

Arrays

There are n mountains in a row, and each mountain has a height. You are given an integer array height where height[i] represents the height of mountain i, and an integer threshold.

A mountain is called stable if the mountain just before it (if it exists) has a height strictly greater than threshold. Note that mountain 0 is not stable.

Return an array containing the indices of all stable mountains in any order.

Example 1:

Input: height = [1,2,3,4,5], threshold = 2

Output: [3,4]

Explanation:

Mountain 3 is stable because height[2] == 3 is greater than threshold == 2.
Mountain 4 is stable because height[3] == 4 is greater than threshold == 2.

Example 2:

Input: height = [10,1,10,1,10], threshold = 3

Output: [1,3]

Example 3:

Input: height = [10,1,10,1,10], threshold = 10

Output: []

Constraints:

2 <= n == height.length <= 100
1 <= height[i] <= 100
1 <= threshold <= 100

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 possible value ranges for the integers in the input array? Can they be negative, zero, or extremely large?
Is there a minimum size for the input array? Should I expect empty or single-element arrays, and how should I handle those cases?
If no "stable mountain" exists within the array, what should I return? Should I return an empty list, null, or throw an exception?
If there are multiple "stable mountains" in the array, should I return all of their starting indices, or just the index of the first one encountered?
Could you define more formally what constitutes a "stable mountain"? Specifically, what are the exact conditions on the surrounding elements (before the peak and after the valley) that determine its stability?

Brute Force Solution

Approach

We are given a set of numbers that represent the height of a mountain range. To find 'stable mountains' using brute force, we'll check every possible combination of starting and ending points to see if they form a stable mountain.

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

Start by considering the very first number as the potential start of a mountain.
Then, for each possible end point from the start to the end of the numbers, check if the numbers in between form a stable mountain.
To check if a section of the numbers forms a stable mountain, see if it goes up, reaches a peak, and then goes down.
Keep track of the starting and ending points of all the sections that are indeed stable mountains.
Repeat the whole process by starting at the second number, the third number, and so on, until you've checked all possible starting points.
In the end, you'll have a collection of all the places where stable mountains exist within the numbers.

Code Implementation

def find_stable_mountains_brute_force(heights):
    stable_mountain_indices = []
    number_of_heights = len(heights)

    for start_index in range(number_of_heights):
        for end_index in range(start_index, number_of_heights):
            # Need at least 3 points to form a mountain
            if end_index - start_index + 1 >= 3:
                sub_array = heights[start_index:end_index + 1]
                is_stable = is_mountain(sub_array)

                #If subarray is a stable mountain, store indices
                if is_stable:
                    stable_mountain_indices.append((start_index, end_index))

    return stable_mountain_indices

def is_mountain(sub_array):
    increasing = True
    peak_found = False

    if len(sub_array) < 3:
        return False

    for i in range(1, len(sub_array)):       
        if increasing:
            #Determine if reached the peak
            if sub_array[i] < sub_array[i - 1]:
                increasing = False
                peak_found = True
            elif sub_array[i] == sub_array[i - 1]:
                return False
        else:
            #Check if decreasing after the peak
            if sub_array[i] >= sub_array[i - 1]:
                return False

    # The mountain must have a peak
    if not peak_found:
        return False

    return not increasing

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible starting points of the mountain range using a loop that runs up to n times, where n is the number of elements in the array. For each starting point, it iterates through all possible ending points, resulting in another loop that runs up to n times. Inside these nested loops, the algorithm checks if the selected range forms a stable mountain, which requires iterating through the range again (worst case up to n times) to confirm it increases to a peak and then decreases. Thus the complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The provided algorithm iterates through the input array and checks for stable mountains. It keeps track of the starting and ending indices of stable mountains. The algorithm does not explicitly use any auxiliary data structures whose size scales with the input size N (the number of heights in the mountain range). The extra memory consists of a few variables to store indices, which is independent of the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to quickly find the starting points of 'mountains' within a sequence, focusing on sections that first increase and then decrease. We avoid unnecessary checks by efficiently identifying these stable mountain patterns. This involves identifying increasing sections and then checking for the peak and decreasing section that completes the mountain.

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

Start at the beginning of the sequence.
Look for an increasing section - a series of values that are each bigger than the one before it.
If you find an increasing section, keep going until you reach a peak - a value that's bigger than its neighbors on both sides.
Once you have a peak, look for a decreasing section - a series of values that are each smaller than the one before it.
If you find a decreasing section after the peak, this confirms you have a 'mountain'.
Record the starting point of the increasing section as the beginning of the mountain.
Move past the end of the mountain (the end of the decreasing section) and continue searching for the next mountain.

Code Implementation

def find_stable_mountains(sequence):
    mountain_indices = []
    index = 0

    while index < len(sequence) - 1:
        # Attempt to find an increasing section.
        start_of_increase = index
        while index < len(sequence) - 1 and sequence[index] < sequence[index + 1]:
            index += 1

        # A peak must exist to continue.
        if start_of_increase == index:
            index += 1
            continue

        # Find the peak of the mountain.
        peak_index = index

        # Find a decreasing section after the peak.
        while index < len(sequence) - 1 and sequence[index] > sequence[index + 1]:
            index += 1

        # Decreasing section must exist after peak to be a mountain
        if peak_index == index:
            index += 1
            continue

        mountain_indices.append(start_of_increase)
        index += 1

    return mountain_indices

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input sequence of size n. While there are loops to identify increasing and decreasing sections, and a peak, these loops are nested such that each element is visited at most a constant number of times. Therefore the time complexity is driven by a single pass through the data, so the operations scale linearly with the input size n. The total operations approximate to c * n, which simplifies to O(n).

Space Complexity

O(1) – The algorithm described only uses a few integer variables to keep track of the current position and potentially the start index of a mountain. No auxiliary data structures that scale with the input size are created. Therefore, the space used is constant regardless of the input sequence length N.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return an empty list to avoid NullPointerException
Input array of length less than 3	Return an empty list as a stable mountain requires at least 3 elements
Array with all elements equal	Return an empty list, since there will be no peak in an array with all equal values
Large array with monotonically increasing or decreasing values	The peak finding algorithm must efficiently identify the absence of a peak and avoid worst-case O(n) iteration
Integer overflow when calculating differences between elements	Use long or double data types for intermediate calculations to prevent overflow issues.
Input array contains negative numbers	The peak finding and stability check algorithms should correctly handle negative number inputs.
Input contains maximum integer values	Ensure comparisons and calculations handle Integer.MAX_VALUE without overflow or unexpected behavior.
Multiple stable mountains exist in the input array	The algorithm should identify and return all the starting indices of each valid stable mountain.

Null input array

How to Handle:

Throw an IllegalArgumentException or return an empty list to avoid NullPointerException

Input array of length less than 3

How to Handle:

Return an empty list as a stable mountain requires at least 3 elements

Array with all elements equal

How to Handle:

Return an empty list, since there will be no peak in an array with all equal values

Large array with monotonically increasing or decreasing values

How to Handle:

The peak finding algorithm must efficiently identify the absence of a peak and avoid worst-case O(n) iteration

Integer overflow when calculating differences between elements

How to Handle:

Use long or double data types for intermediate calculations to prevent overflow issues.

Input array contains negative numbers

How to Handle:

The peak finding and stability check algorithms should correctly handle negative number inputs.

Input contains maximum integer values

How to Handle:

Ensure comparisons and calculations handle Integer.MAX_VALUE without overflow or unexpected behavior.

Multiple stable mountains exist in the input array

How to Handle:

The algorithm should identify and return all the starting indices of each valid stable mountain.

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 possible value ranges for the integers in the input array? Can they be negative, zero, or extremely large?
Is there a minimum size for the input array? Should I expect empty or single-element arrays, and how should I handle those cases?
If no "stable mountain" exists within the array, what should I return? Should I return an empty list, null, or throw an exception?
If there are multiple "stable mountains" in the array, should I return all of their starting indices, or just the index of the first one encountered?
Could you define more formally what constitutes a "stable mountain"? Specifically, what are the exact conditions on the surrounding elements (before the peak and after the valley) that determine its stability?

Brute Force Solution

Approach

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

Start by considering the very first number as the potential start of a mountain.
Then, for each possible end point from the start to the end of the numbers, check if the numbers in between form a stable mountain.
To check if a section of the numbers forms a stable mountain, see if it goes up, reaches a peak, and then goes down.
Keep track of the starting and ending points of all the sections that are indeed stable mountains.
Repeat the whole process by starting at the second number, the third number, and so on, until you've checked all possible starting points.
In the end, you'll have a collection of all the places where stable mountains exist within the numbers.

Code Implementation

def find_stable_mountains_brute_force(heights):
    stable_mountain_indices = []
    number_of_heights = len(heights)

    for start_index in range(number_of_heights):
        for end_index in range(start_index, number_of_heights):
            # Need at least 3 points to form a mountain
            if end_index - start_index + 1 >= 3:
                sub_array = heights[start_index:end_index + 1]
                is_stable = is_mountain(sub_array)

                #If subarray is a stable mountain, store indices
                if is_stable:
                    stable_mountain_indices.append((start_index, end_index))

    return stable_mountain_indices

def is_mountain(sub_array):
    increasing = True
    peak_found = False

    if len(sub_array) < 3:
        return False

    for i in range(1, len(sub_array)):       
        if increasing:
            #Determine if reached the peak
            if sub_array[i] < sub_array[i - 1]:
                increasing = False
                peak_found = True
            elif sub_array[i] == sub_array[i - 1]:
                return False
        else:
            #Check if decreasing after the peak
            if sub_array[i] >= sub_array[i - 1]:
                return False

    # The mountain must have a peak
    if not peak_found:
        return False

    return not increasing

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 sequence.
Look for an increasing section - a series of values that are each bigger than the one before it.
If you find an increasing section, keep going until you reach a peak - a value that's bigger than its neighbors on both sides.
Once you have a peak, look for a decreasing section - a series of values that are each smaller than the one before it.
If you find a decreasing section after the peak, this confirms you have a 'mountain'.
Record the starting point of the increasing section as the beginning of the mountain.
Move past the end of the mountain (the end of the decreasing section) and continue searching for the next mountain.

Code Implementation

def find_stable_mountains(sequence):
    mountain_indices = []
    index = 0

    while index < len(sequence) - 1:
        # Attempt to find an increasing section.
        start_of_increase = index
        while index < len(sequence) - 1 and sequence[index] < sequence[index + 1]:
            index += 1

        # A peak must exist to continue.
        if start_of_increase == index:
            index += 1
            continue

        # Find the peak of the mountain.
        peak_index = index

        # Find a decreasing section after the peak.
        while index < len(sequence) - 1 and sequence[index] > sequence[index + 1]:
            index += 1

        # Decreasing section must exist after peak to be a mountain
        if peak_index == index:
            index += 1
            continue

        mountain_indices.append(start_of_increase)
        index += 1

    return mountain_indices

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return an empty list to avoid NullPointerException
Input array of length less than 3	Return an empty list as a stable mountain requires at least 3 elements
Array with all elements equal	Return an empty list, since there will be no peak in an array with all equal values
Large array with monotonically increasing or decreasing values	The peak finding algorithm must efficiently identify the absence of a peak and avoid worst-case O(n) iteration
Integer overflow when calculating differences between elements	Use long or double data types for intermediate calculations to prevent overflow issues.
Input array contains negative numbers	The peak finding and stability check algorithms should correctly handle negative number inputs.
Input contains maximum integer values	Ensure comparisons and calculations handle Integer.MAX_VALUE without overflow or unexpected behavior.
Multiple stable mountains exist in the input array	The algorithm should identify and return all the starting indices of each valid stable mountain.

Null input array

How to Handle:

Throw an IllegalArgumentException or return an empty list to avoid NullPointerException

Input array of length less than 3

How to Handle:

Return an empty list as a stable mountain requires at least 3 elements

Array with all elements equal

How to Handle:

Return an empty list, since there will be no peak in an array with all equal values

Large array with monotonically increasing or decreasing values

How to Handle:

The peak finding algorithm must efficiently identify the absence of a peak and avoid worst-case O(n) iteration

Integer overflow when calculating differences between elements

How to Handle:

Use long or double data types for intermediate calculations to prevent overflow issues.

Input array contains negative numbers

How to Handle:

The peak finding and stability check algorithms should correctly handle negative number inputs.

Input contains maximum integer values

How to Handle:

Ensure comparisons and calculations handle Integer.MAX_VALUE without overflow or unexpected behavior.

Multiple stable mountains exist in the input array

How to Handle:

The algorithm should identify and return all the starting indices of each valid stable mountain.

0/1916 Google questions completed

0/1916 completed