Peak Index in a Mountain Array Solutions in C++

// Source : https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
// Author : Hao Chen
// Date   : 2018-06-29



class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        
        // Put two dummy items at head and tail to avoid Out-of-Bound Error.
        #define INT_MAX 2147483647
        #define INT_MIN (-INT_MAX - 1)
        A.insert ( A.begin() , INT_MIN );
        A.push_back(INT_MIN);
        
        //binary search
        int len = A.size();
        int left = 1, right = len - 2;
        while(left <= right) {
            int mid = left + (right - left)/2; //avoid integer overflow
            if ( A[mid-1] < A[mid] && A[mid] > A[mid+1]) return mid-1;
            if ( A[mid-1] < A[mid] && A[mid] < A[mid+1]) left = mid + 1;
            if ( A[mid-1] > A[mid] && A[mid] > A[mid+1]) right = mid - 1;
            
        }
        return -1;
    }
};

/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
/// Author : liuyubobobo
/// Time   : 2018-06-17

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Two Linear Scans
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {

        int maxValue = A[0];
        for(int a: A)
            maxValue = max(maxValue, a);

        for(int i = 0 ; i < A.size() ; i ++)
            if(A[i] == maxValue)
                return i;

        assert(false);
        return -1;
    }
};

int main() {

    vector<int> nums1 = {0, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums1) << endl;

    vector<int> nums2 = {0, 2, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums2) << endl;

    return 0;
}

/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
/// Author : liuyubobobo
/// Time   : 2018-06-16

#include <iostream>
#include <vector>

using namespace std;

/// One Linear Scan
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {

        for(int i = 1 ; i < A.size() ; i ++)
            if(A[i - 1] > A[i])
                return i - 1;
        return A.size() - 1;
    }
};

int main() {

    vector<int> nums1 = {0, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums1) << endl;

    vector<int> nums2 = {0, 2, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums2) << endl;

    return 0;
}

/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
/// Author : liuyubobobo
/// Time   : 2018-06-17

#include <iostream>
#include <vector>

using namespace std;

/// Binary Search
/// Make an array of [True, True, ... , True, False, False, ... , False]
/// Find the largest index which is True
///
/// Time Complexity: O(logn)
/// Space Complexity: O(n)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {

        vector<bool> vec;
        for(int i = 1 ; i < A.size() ; i ++)
            vec.push_back(A[i-1] < A[i]);

        int l = 0, r = vec.size() - 1;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if(vec[mid])
                l = mid;
            else
                r = mid - 1;
        }
        return l + 1;
    }
};

int main() {

    vector<int> nums1 = {0, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums1) << endl;

    vector<int> nums2 = {0, 2, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums2) << endl;

    return 0;
}

/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
/// Author : liuyubobobo
/// Time   : 2018-06-17

#include <iostream>
#include <vector>

using namespace std;

/// Binary Search in A directly
/// Time Complexity: O(logn)
/// Space Complexity: O(n)
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {

        int l = 0, r = A.size() - 1;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if(A[mid - 1] < A[mid])
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
};

int main() {

    vector<int> nums1 = {0, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums1) << endl;

    vector<int> nums2 = {0, 2, 1, 0};
    cout << Solution().peakIndexInMountainArray(nums2) << endl;

    return 0;
}