Problem 941

Abstract / Summary

Check if an array strictly increases then strictly decreases with at least three elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0941.py

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        if len(arr) < 3:
            return False
        if arr[0] >= arr[1] or arr[-1] >= arr[-2]:
            return False

        pos = 1
        while arr[pos - 1] < arr[pos]:
            pos += 1
        while pos < len(arr) and arr[pos - 1] > arr[pos]:
            pos += 1

        return pos == len(arr)
14 lines | 402 bytes | submitted October 7, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 35% (1+ million submissions).

Typical patterns to solve this problem:
  • Array
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation determines whether a given integer list conforms to the definition of a mountain array. A mountain array must contain at least three elements, strictly increase to a single peak, and then strictly decrease. The algorithm proceeds through a series of straightforward checks and two linear scans that together verify the required shape without allocating additional memory.

Initial Validation

The first guard clause checks the length of the input. If the list contains fewer than three elements, it cannot satisfy the mountain criteria, and the function returns False immediately.

if len(arr) < 3:
    return False

The next condition ensures that the array does not start with a non-increasing pair and does not end with a non-decreasing pair. By examining the first two and the last two elements, the code eliminates cases where the array begins with a plateau or a descent, or ends with a plateau or an ascent.

if arr[0] >= arr[1] or arr[-1] >= arr[-2]:
    return False

These early exits prevent unnecessary processing for inputs that are clearly invalid.

Ascending Phase

A variable pos is initialized to the second index, representing the current position in the scan. The first while loop advances pos while the sequence is strictly increasing. The loop condition arr[pos - 1] < arr[pos] guarantees that each step moves forward only when the monotonic increase holds.

pos = 1
while arr[pos - 1] < arr[pos]:
    pos += 1

When the loop terminates, pos points to the first element that is not greater than its predecessor, which is either the peak or the point where the increase stops.

Descending Phase

The second while loop continues from the current pos and moves forward while the sequence is strictly decreasing. The condition arr[pos - 1] > arr[pos] enforces the required descent.

while pos < len(arr) and arr[pos - 1] > arr[pos]:
    pos += 1

The additional bound check pos < len(arr) prevents an index error when the array ends with a decreasing segment.

Final Verification

After both scans, the algorithm verifies that the entire array has been consumed. If pos equals the length of the array, the input satisfied a single rising segment followed by a single falling segment, and the function returns True. Any leftover elements indicate a violation of the mountain shape, resulting in False.

return pos == len(arr)

Edge Cases Handled

The code gracefully handles several subtle scenarios:

  • Arrays that start with a plateau ([2, 2, 3, 2, 1]) are rejected by the early boundary check.
  • Arrays that end with a plateau ([1, 2, 3, 3]) are also rejected by the same check.
  • Purely increasing arrays ([1, 2, 3, 4]) pass the ascending loop but fail the final verification because the descending loop never advances, leaving pos short of the array length.
  • Purely decreasing arrays ([5, 4, 3, 2]) are caught by the initial boundary condition that requires the first element to be less than the second.
  • Arrays with multiple peaks ([1, 3, 2, 4, 1]) cause the descending loop to stop at the first valley, leaving remaining elements unprocessed, and thus the final check fails.
  • Single-element peaks at the ends ([3, 2, 1] or [1, 2, 3]) are eliminated by the early checks that require a proper rise before a fall.

Performance Optimizations

The implementation achieves optimal performance through several deliberate choices:

  • Early exits eliminate work for clearly invalid inputs, reducing the number of iterations for short or malformed arrays.
  • Single pass scanning: both the ascent and descent are performed in a single linear traversal without resetting indices or revisiting elements.
  • Minimal state: only one integer variable (pos) tracks progress, avoiding additional data structures or auxiliary arrays.
  • In-place comparisons: the algorithm accesses elements directly by index, which is efficient in Python because list indexing is O(1).
  • Bounded loop conditions: the second loop includes an explicit length check, preventing out-of-range access without requiring a separate sentinel value.

These characteristics ensure that the function runs in linear time relative to the input size while using constant extra space.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long line of numbered building blocks. You want to see if these blocks make a shape that goes up like a mountain and then comes back down.

First, the code checks to see if there are at least three blocks in the line. If there are fewer than three, the shape cannot be a mountain. Then, it checks the ends of the line. If the very first block is bigger than the second one, or if the very last block is bigger than the one next to it, the path cannot climb up and down correctly.

Next, the code starts walking along the blocks one by one. It looks at the numbers and keeps moving forward as long as the next block is taller than the one before it. This represents the hike up the mountain. Once the blocks stop getting taller, the code starts walking down the other side. It keeps moving as long as the next block is shorter than the one before it.

If the code finishes its walk exactly at the very last block, it means the path went up and then down without any flat parts or little bumps, just like a perfect mountain.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.59 | σ = 1.16

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
Dijkstra-Edu Java
everthis JS
fartem Ruby
fengvyi C++
fsq C++
haoel Python
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
MacJim C++
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
Dijkstra-Edu Java
everthis JavaScript
fartem Ruby
fengvyi C++
fsq C++
haoel Python
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
MacJim C++
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
36 links | 23 authors | 8 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

2 easy 5 medium 1 hard
9 solutions   October 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality