845.longest-mountain-in-array.md

845. Longest Mountain in Array

Two Pointers

We iterate the starting point to climb, then try to finish the mountain. If we can find the peak and the down side, then we can calculate the length of the mountain.

In this problem, we should always let i stop at the starting point of the mountain. If there is any invalid position, we should skip it and stay at the last of invalid position, because the next position might be the starting point of the mountain.

// Group by consecutive pattern
fun longestMountain(arr: IntArray): Int {
    if (arr.size < 3) return 0
    var ans = 0
    var i = 0
    while (i < arr.size) {
        // Skip invalid positionz
        // 1, 1, 0, 0, 2
        //          i
        while (i + 1 < arr.size && arr[i] >= arr[i + 1]) i++

        // Start of the mountain
        // Please note that we should always let `i` stop at the starting point of the mountain.
        val start = i
        var up = false
        while (i + 1 < arr.size && arr[i] < arr[i + 1]) {
            up = true
            i++
        }
        var down = false
        while (i + 1 < arr.size && arr[i] > arr[i + 1]) {
            down = true
            i++
        }
        // `i` will stop at the last position of the mountain.

        if (up && down) {
            ans = maxOf(ans, i - start + 1)
        } else {
            i++
        }
    }
    return ans
}

The following implementation is more complex, might skip them.

def longestMountain(self, arr: List[int]) -> int:
    n = len(arr)
    start = 0
    end = 0
    max_length = 0
    while start < n:
        if start + 1 < n and arr[start] < arr[start + 1]:
            end = start
            while end + 1 < n and arr[end] < arr[end + 1]:
                end += 1
            if end + 1 < n and arr[end] > arr[end + 1]:
                while end + 1 < n and arr[end] > arr[end + 1]:
                    end += 1
                max_length = max(max_length, end - start + 1)
            start = end
        else:
            start += 1
    return max_length

fun longestMountain(arr: IntArray): Int {
    var start = 0
    var end = 0
    var maxLength = 0
    while (start < arr.size) {
        // We find the starting point to climb
        if (start + 1 < arr.size && arr[start] < arr[start + 1]) {
            end = start
            // Keep going up to find the peak
            while (end + 1 < arr.size && arr[end] < arr[end + 1]) {
                end++
            }
            // Then start to go down
            if (end + 1 < arr.size && arr[end] > arr[end + 1]) {
                // Keep going down
                while (end + 1 < arr.size && arr[end] > arr[end + 1]) {
                    end++
                }
                maxLength = max(maxLength, end - start + 1)
            }
            // Move to next position to seek the next mountain.
            start = end
        } else {
            start++
        }
    }
    return maxLength
}

// Or same idea with the same implementation of [941. Valid Mountain Array](941.valid-mountain-array.md)
fun longestMountain(arr: IntArray): Int {
    var longest = 0
    if (arr.size < 3) return 0
    var start = 0
    var end = 0
    while (start + 1 < arr.size) {
        // Find the starting point to climb
        if (arr[start] < arr[start + 1]) {
            end = start + 1
            var goUp = false
            var goDown = false
            // Try to finish the mountain
            while (end < arr.size) {
                if (arr[end - 1] < arr[end]) {
                    if (goDown) break
                    goUp = true
                } else if (arr[end - 1] > arr[end]) {
                    if (!goUp) break
                    goDown = true
                } else {
                    break
                }
                end++
            }
            // If we find the valid mountain
            if (goUp && goDown) {
                longest = maxOf(longest, end - start)
            }
            // End - 1 because `end` is the first element that breaks the mountain, so we need to go back one step.
            start = end - 1
        } else {
            start++
        }
    }
    return longest
}

• Time Complexity: O(n).
• Space Complexity: O(1).