Approach #1: Two Pointer [Accepted]
Without loss of generality, a mountain can only start after the previous one ends.
This is because if it starts before the peak, it will be smaller than a mountain starting previous; and it is impossible to start after the peak.
For a starting index
base, let's calculate the length of the longest mountain
A[base], A[base+1], ..., A[end].
If such a mountain existed, the next possible mountain will start at
base = end; if it didn't, then either we reached the end, or we have
A[base] > A[base+1] and we can start at
base + 1.
Here is a worked example on the array
A = [1, 2, 3, 2, 1, 0, 2, 3, 1]:
base starts at
end travels using the first while loop to
end = 2 (
A[end] = 3), the potential peak of this mountain. After, it travels to
end = 5 (
A[end] = 0) during the second while loop, and a candidate answer of 6
(base = 0, end = 5) is recorded.
Afterwards, base is set to
5 and the process starts over again, with
end = 7 the peak of the mountain, and
end = 8 the right boundary, and the candidate answer of 4
(base = 5, end = 8) being recorded.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.