Java

/**

 852. Peak Index in a Mountain Array

 Let's call an array A a mountain if the following properties hold:

 A.length >= 3
 There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
 Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

 Example 1:

 Input: [0,1,0]
 Output: 1
 Example 2:

 Input: [0,2,1,0]
 Output: 1
 Note:

 3 <= A.length <= 10000
 0 <= A[i] <= 10^6
 A is a mountain, as defined above.

 @tag-array

 */

public class Peak_Index_in_a_Mountain_Array {

    class Solution {
        public int peakIndexInMountainArray(int[] A) {
            int i = 0;
            while (A[i] < A[i+1]) {
                i++;
            }
            return i;
        }
    }

    class Solution_BinarySearch {
        public int peakIndexInMountainArray(int[] A) {

            if (A == null || A.length == 0) {
                return 0;
            }

            int i = 0;
            int j = A.length - 1;

            while (i < j) {
                int mid = (i + j) / 2;

                if (mid + 1 < A.length && A[mid + 1] > A[mid]) {
                    i = mid + 1;
                }
                else if (mid + 1 < A.length && A[mid + 1] < A[mid]) {
                    j = mid;
                }
                else if (mid + 1 < A.length && A[mid - 1] == A[mid]) {
                    i++;
                }
            }

            return i;
        }
    }
}

// OJ: https://leetcode.com/problems/peak-index-in-a-mountain-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int i = 1;
        while (i < A.size() && A[i] > A[i - 1]) ++i;
        return i - 1;
    }
};

class Solution(object):
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        left, right = 0, len(A) - 1
        while left < right:
            mid = (left + right) / 2
            if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
                left = mid
            elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
                right = mid
            else:
                break
        return mid

Java

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int length = A.length;
        for (int i = 1; i < length; i++) {
            if (A[i] < A[i - 1])
                return i - 1;
        }
        return -1;
    }
}

// OJ: https://leetcode.com/problems/peak-index-in-a-mountain-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int i = 1;
        while (i < A.size() && A[i] > A[i - 1]) ++i;
        return i - 1;
    }
};

class Solution(object):
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        left, right = 0, len(A) - 1
        while left < right:
            mid = (left + right) / 2
            if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
                left = mid
            elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
                right = mid
            else:
                break
        return mid

852 - Peak Index in a Mountain Array

All Problems

All Solutions