/*
  LeetCode 162. Find Peak Element
   A peak element is an element that is strictly greater than its neighbors.

   Given a 0-indexed integer array nums, find a peak element, and return its index. If the
   array contains multiple peaks, return the index to any of the peaks.

   You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always
   considered to be strictly greater than a neighbor that is outside the array.

   You must write an algorithm that runs in O(log n) time.

   Example 1:
   Input: nums = [1,2,3,1]
   Output: 2

   Explanation: 3 is a peak element and your function should return the index number 2.

   Example 2:
   Input: nums = [1,2,1,3,5,6,4]
   Output: 5

   Explanation: Your function can return either index number 1 where the peak element is 2, or index
   number 5 where the peak element is 6.

   Constraints:

   1 <= nums.length <= 1000
   -231 <= nums[i] <= 231 - 1
   nums[i] != nums[i + 1] for all valid i.


   Most Expected Solution in Bloomberg-style Interview: Binary Search (O(log n))
   Key Insight  
      Because we only need any peak and the array has the property that adjacent elements
      differ, we can use binary search by looking at the slope:

      If nums[mid] < nums[mid+1] → we're on an ascending slope → a peak must exist on the right side (including mid+1)
      If nums[mid] > nums[mid+1] → we're on a descending slope or at a peak → a peak exists on the left side (including mid)

   This works beautifully because of the -∞ boundaries and the no-equal-adjacent guarantee.
   
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

int findPeakLinear(const vector<int>& arr)
{
    if (arr.size() == 1)
        return 0;
    
    // check first and last element
    if (arr[0] > arr[1])
        return 0;
    
    if (arr[arr.size()-1] > arr[arr.size()-2])
        return arr.size()-1;
    
    for (size_t i = 1; i < arr.size() - 1; i++)
        if (arr[i] > arr[i-1] && arr[i] > arr[i+1])
            return i;

    return -1;
}

int findPeakLinear1(const vector<int>& arr)
{
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return (int)i;
        }
    }
    return (int) arr.size() - 1;  // last element is peak if we reach here
}

int findPeakBinarySearch(const vector<int>& arr)
{
    int left = 0;
    int right = arr.size() - 1;
        
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        
        if (arr[mid + 1] > arr[mid])
        {
            left = mid + 1;  // Ascending: peak on right
        }
        else
        {
            right = mid;     // Descending: peak on left or at mid
        }
    }
    
    return left;    
}

int main(void)
{
    vector<tuple<vector<int>, vector<int>>> testCases =
        {
            // input arr         index
            { {1,2,3,1},         {2}     },
            { {1,2,1,3,5,6,4},   {1,5}   },
            { {1,3,2,5,4,6,7,0}, {1,3,6} },
            { {7},               {0}     },
            { {1,2,3,4,5},       {4}     },
            { {5,4,3,2,1},       {0}     },
            { {10,1,2,3},        {0,3}   }, // Peak at start and end
            { {1,2,3,10},        {3}     }, // Peak at end
        };
    
    for (const auto& testCase: testCases)
    {
        int idx;
        string s;

        idx = findPeakLinear(get<0>(testCase));
        cout << setw(22) << right << "findPeakLinear: ";
        for (auto& i: get<0>(testCase)) s += to_string(i) + " ";
        cout << setw(20) << left << s;
        
        cout << "index: " << idx << " possible soln: ";
        for (auto& i: get<1>(testCase)) cout << i << " ";
        cout << endl;

        s.clear();
        
        idx = findPeakLinear1(get<0>(testCase));
        cout << setw(22) << right << "findPeakLinear1: ";
        for (auto& i: get<0>(testCase)) s += to_string(i) + " ";
        cout << setw(20) << left << s;
        
        cout << "index: " << idx << " possible soln: ";
        for (auto& i: get<1>(testCase)) cout << i << " ";
        cout << endl;
        
        s.clear();
        
        idx = findPeakBinarySearch(get<0>(testCase));
        cout << setw(22) << right << "findPeakBinarySearch: ";
        for (auto& i: get<0>(testCase)) s += to_string(i) + " ";
        cout << setw(20) << left << s;
        
        cout << "index: " << idx << " possible soln: ";
        for (auto& i: get<1>(testCase)) cout << i << " ";
        cout << endl;
    }
    
    return 0;
}