cyberangles blog

Find whether a subarray is in form of a mountain or not

In the realm of array - based algorithms, one common and interesting problem is to determine whether a given subarray is in the form of a mountain. A mountain subarray has a characteristic shape where the elements first increase until they reach a peak and then start decreasing. This problem has applications in various fields such as financial market analysis, terrain modeling, and signal processing. Understanding how to solve this problem efficiently can improve your algorithmic thinking and your ability to handle real - world data scenarios. In this blog, we will dive deep into the problem, discuss common approaches, and provide code examples to solve it.

2026-07

Table of Content#

  1. What is a Mountain Subarray?
  2. Common Practices for Detection
  3. Step - by - Step Algorithm
  4. Example Usage
  5. Best Practices
  6. Complexity Analysis
  7. Conclusion
  8. References

What is a Mountain Subarray?#

A mountain subarray is a contiguous part of an array that satisfies the following conditions:

  • It has at least 3 elements.
  • There exists an index i (where 0 < i < n - 1, and n is the length of the subarray) such that the elements from the start of the subarray up to the i - th element are in strictly increasing order, and the elements from the i+1 - th element to the end of the subarray are in strictly decreasing order.

For example, in the array [2, 3, 5, 4, 3], the subarray [2, 3, 5, 4, 3] is a mountain subarray as it first increases (2 -> 3 -> 5) and then decreases (5 -> 4 -> 3).

Common Practices for Detection#

Two - Pointer Approach#

One of the common ways to check if a subarray is a mountain is by using the two - pointer approach. The basic idea is to start a pointer at the beginning of the subarray, move it forward as long as the elements are increasing. Then, start another pointer from the end of the subarray, move it backwards as long as the elements are decreasing. If the two pointers meet at a non - boundary position, then the subarray is a mountain.

Single - Pass Approach#

Another approach is to do a single pass through the subarray. First, find the peak element of the subarray. Check if the elements before the peak are in increasing order and the elements after the peak are in decreasing order.

Step - by - Step Algorithm#

We will use the single - pass approach here.

  1. Validate length: Check if the subarray has at least 3 elements. If not, return False as a mountain subarray must have at least 3 elements.
  2. Find the peak: Traverse the subarray from left to right until you find the first element such that the next element is smaller. This element is the peak. If there is no such element (i.e., the array is always increasing), return False.
  3. Check the decreasing part: After finding the peak, continue traversing the subarray. The remaining elements should be in strictly decreasing order. If at any point an element is not smaller than the previous one, return False.
  4. Boundary check: Also, make sure that the peak is not the first or the last element of the subarray. If it is, return False.
  5. Return result: If all the above conditions are satisfied, return True.

Example Usage#

Here is the Python code to implement the above algorithm:

def is_mountain_subarray(arr):
    n = len(arr)
    # Step 1: Validate length
    if n < 3:
        return False
    # Step 2: Find the peak
    i = 1
    while i < n and arr[i] > arr[i - 1]:
        i += 1
    if i == 1 or i == n:
        return False
    # Step 3: Check the decreasing part
    while i < n and arr[i] < arr[i - 1]:
        i += 1
    # Step 4 and 5: If we reached the end, it's a mountain
    return i == n
 
# Example usage
arr = [2, 3, 5, 4, 3]
print(is_mountain_subarray(arr))  # Output: True
 
arr = [2, 3, 5]
print(is_mountain_subarray(arr))  # Output: False

Best Practices#

  • Input Validation: Always check the input length before proceeding with the main logic. As a mountain subarray must have at least 3 elements, this initial check can save unnecessary processing.
  • Code Readability: Use meaningful variable names like i in the traversal to keep the code easy to understand. Add comments to explain each step of the algorithm.
  • Modularity: If the function is part of a larger program, make it modular so that it can be easily reused in different parts of the code.

Complexity Analysis#

  • Time Complexity: The algorithm has a time complexity of $O(n)$, where n is the length of the subarray. This is because we traverse the subarray only once.
  • Space Complexity: The space complexity is $O(1)$ as we only use a constant amount of extra space.

Conclusion#

Determining whether a subarray is in the form of a mountain is a straightforward yet important problem. By using the single - pass approach described above, we can efficiently solve this problem with linear time complexity. Following the best practices will make your code more robust and easier to maintain.

References#

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Python official documentation: https://docs.python.org/3/