Posted on Apr 21, 2020

Day-9 Valid Mountain Array

This problem is a part of Introduction to Data Structures Fun with Arrays - 101. Sub-heading of the section is searching for the items in an array.

Problem Statement

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

Observations

Elements should be strictly increasing. Then a peak occurs, followed by a steady decrease.
There can not be multiple mountain peaks in the array. Hence, if there exists a peak. The pattern would be as mentioned in point 1 above.
The minimum number of elements in the array for a mountain peak to exist would be 3.

Solution Approach

First, check the length of the array. Only if it is greater than 3. Then check the next conditions.
Find the peak. The peak would be the point after which the value of elements strictly starts to strictly decrease.
Be careful of the position of starting and ending in subsequent loops.

class Solution: def validMountainArray(self, A: List[int]) -> bool: result = False if len(A) >= 3: for x in range(0, len(A)-1): if A[x+1] > A[x]: result = True else: break if result: for index in range(x, len(A)-1): if (A[index+1] < A[index]): result = True else: result = False break return result

Learnings

Time complexity - O(n)
Solve multiple scenarios using a pen and paper first. Then code. :)

Top comments (4)

Ahmedur Rahman Shovon • Apr 22 '20 • Edited

This problem can be found in Leetcode: leetcode.com/problems/valid-mounta...

My approach with test case:

class Solution: def validMountainArray(self, arr: List[int]) -> bool: peak_found = False for i in range(1, len(arr)): if arr[i] == arr[i-1]: return False if arr[i] < arr[i-1]: if peak_found == False: if i == 1: return False else: peak_found = True else: if peak_found == True: return False return peak_found if __name__ == "__main__": solution = Solution() test_case = [0, 2, 3, 4, 5, 2, 1, 0] accepted_result = True result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 2, 3, 3, 5, 2, 1, 0] accepted_result = False result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 1, 2, 3, 2, 1] accepted_result = True result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 2, 3, 4, 5, 2, 1, 5, 4, 1] accepted_result = False result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 2, 3, 4, 5, 2, 1, 3, 2, 1] accepted_result = False result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 2, 1] accepted_result = True result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [0, 2, 3] accepted_result = False result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result) test_case = [5, 2, 1] accepted_result = False result = solution.validMountainArray(test_case) assert result == accepted_result, (test_case, accepted_result, result)