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)
Difficulty
and has an acceptance rate of about 35% (1+ million submissions).
Typical patterns to solve this problem:
- Array
AI Disclaimer
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.
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, leavingposshort 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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Solved On The Same Day
- problem 821: Shortest Distance to a Character
- problem 1037: Valid Boomerang
- problem 553: Optimal Division
- problem 593: Valid Square
- problem 752: Open the Lock
- problem 833: Find And Replace in String
- problem 970: Powerful Integers
- problem 132: Palindrome Partitioning II
Extra
- 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