loading...

Day-9 Valid Mountain Array

mridubhatnagar profile image Mridu Bhatnagar ・1 min read

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.

Alt Text

Observations
  1. Elements should be strictly increasing. Then a peak occurs, followed by a steady decrease.
  2. 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.
  3. The minimum number of elements in the array for a mountain peak to exist would be 3.
Solution Approach
  1. First, check the length of the array. Only if it is greater than 3. Then check the next conditions.
  2. Find the peak. The peak would be the point after which the value of elements strictly starts to strictly decrease.
  3. 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
  1. Time complexity - O(n)
  2. Solve multiple scenarios using a pen and paper first. Then code. :)

Discussion

pic
Editor guide
Collapse
arsho profile image
Ahmedur Rahman Shovon

I assume, [0, 2, 5] and [5, 2, 1] both are valid mountain array.
My approach with test case:

def is_mountain_array(nums):
    is_peak_found = False
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return False
        elif nums[i] < nums[i-1]:
            if not is_peak_found:
                is_peak_found = True
        elif nums[i] > nums[i-1]:
            if is_peak_found:
                return False        
    return True



if __name__ == "__main__":
    test_case = [0, 2, 3, 4, 5, 2, 1, 0]
    accepted_result = True
    result = is_mountain_array(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 = is_mountain_array(test_case)
    assert result == accepted_result, (test_case, accepted_result, result)

    test_case = [0, 1, 2, 3, 2, 1]
    accepted_result = True
    result = is_mountain_array(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 = is_mountain_array(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 = is_mountain_array(test_case)
    assert result == accepted_result, (test_case, accepted_result, result)

    test_case = [0, 2, 1]
    accepted_result = True
    result = is_mountain_array(test_case)
    assert result == accepted_result, (test_case, accepted_result, result)

    test_case = [0, 2, 3]
    accepted_result = True
    result = is_mountain_array(test_case)
    assert result == accepted_result, (test_case, accepted_result, result)

    test_case = [5, 2, 1]
    accepted_result = True
    result = is_mountain_array(test_case)
    assert result == accepted_result, (test_case, accepted_result, result)

Collapse
lautarolobo profile image
Lautaro Lobo

This is a good one! I've done it in Java and C, C was harder (types and all stuff).