[leetcode #941] Valid Mountain Array

Problem

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

・ arr.length >= 3
・ There exists some i with 0 < i < arr.length - 1 such that:
	・ arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
	・ arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

・ 1 <= arr.length <= 10⁴
・ 0 <= arr[i] <= 10⁴

Idea

Brute-force로 풀어도 쉽게 풀리는 문제다. 얼마나 짧게 푸느냐가 관건이겠지만!

주어진 array에서 uphill 한 번, downhill 한 번이 나오는지 확인하면 된다.

어떻게 풀어도 O(N)이 나오지만 loop 내에서 매번 비교를 하면 느릴 수 있다는 걸 다시 한 번 깨닫게 된다.

우선 array의 길이가 3보다 작을 경우 산이 될 수 없다.
그리고 오르막이거나 내리먹이거나 연속된 값이 같을 경우 산이 아니므로 곧바로 false를 리턴한다.
처음엔 오르막이므로 내리막으로 전환되었을 때 오르막 flag를 끄고, 만약 index가 0이면 바로 내리막이 나오는 것이므로 false를 리턴한다.
내리막인 상태에서 연속된 값이 증가할 경우 false를 리턴한다.

마지막에 오르막 플래그가 꺼져 있을 경우 산이다.

그런데 리트코드 풀이를 보니 loop 내에서 비교는 하지 않는다. 오르막이 끝나는 지점의 index 상태를 확인하고, 내리막이 끝나는 지점의 index 상태만을 확인할 뿐이다. 이렇게 풀면 loop 내에서 비교 횟수가 줄어 확실히 효율적으로 동작한다.

Solution

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) {
            return false;
        }

        boolean uphill = true;

        for (int i=0; i < arr.length-1; i++) {
            if (arr[i] == arr[i+1]) {
                return false;
            }

            if (uphill) {
                if (arr[i] > arr[i+1]) {
                    if (i == 0) {
                        return false;
                    }
                    uphill = false;
                }
            } else {
                if (arr[i] < arr[i+1]) {
                    return false;
                }
            }
        }

        return !uphill;
    }
}

아래는 leetcode solution이다.

class Solution {
    public boolean validMountainArray(int[] A) {
        int N = A.length;
        int i = 0;

        // walk up
        while (i+1 < N && A[i] < A[i+1])
            i++;

        // peak can't be first or last
        if (i == 0 || i == N-1)
            return false;

        // walk down
        while (i+1 < N && A[i] > A[i+1])
            i++;

        return i == N-1;
    }
}

Reference

https://leetcode.com/problems/valid-mountain-array/