The "Valid Mountain Array" interview question asks you to determine if a given array of integers follows a specific "mountain" structure. A valid mountain array must have at least three elements and a single peak. It must strictly increase from the start to the peak and then strictly decrease from the peak to the end. There should be no plateaus (equal adjacent elements) and no multiple peaks.
Companies like Uber, Microsoft, and Meta use the "Valid Mountain Array" coding problem to assess a candidate's ability to handle array traversals and multiple conditions in a single pass. It’s a classic "Array interview pattern" problem that requires clean logic to ensure the peak isn't at the very beginning or the very end of the array.
The most efficient algorithmic pattern is the "Single Pass Linear Scan." You can simulate a climber going up the mountain as long as the next element is larger, and then going down as long as the next element is smaller. The key is to ensure the "climb" actually happens and the "descent" also happens, ending exactly at the last index.
Take the array [1, 3, 5, 4, 2].
A common error is not checking if the array has at least three elements. Another frequent mistake is failing to verify that the peak is not the first or last element; for example, [5, 4, 3, 2, 1] or [1, 2, 3, 4, 5] are not valid mountains because they only have a slope, not a peak. Candidates also often miss cases with flat sections like [1, 2, 2, 1].
For the "Valid Mountain Array" coding problem, focus on writing a solution that uses a single while loop or two consecutive while loops. This demonstrates that you can solve the problem in O(n) time and O(1) space, which is the optimal approach interviewers look for.
