# #11 Longest Peak

###### tags:`Array` `Medium`

## Problem
Write a function that takes in an array of integers and returns the length of the longest peak in the array.

A peak is defined as adjacent integers in the array that are strictly increasing until they reach a tip (the highest value in the peak), at which point they become strictly decreasing. At least three integers are required to form a peak.

For example, the integers `1, 4, 10, 2` form a peak, but the integers `4, 0, 10` don't and neither do the integers `1, 2, 2, 0`. Similarly, the integers `1, 2, 3` don't form a peak because there aren't any strictly decreasing integers after the `3`.

### Sample Input

array = [1, 2, 3, 3, 4, 0, 10, 6, 5, -1, -3, 2, 3]

### Sample Output

6 // 0, 10, 6, 5, -1, -3

<br/>

## Solutions

### Official:

// O(n) time | O(1) space - where n is the length of the input array
function longestPeak(array) {
  let longestPeakLength = 0;
  let i = 1;
  while (i < array.length - 1) {
    const isPeak = array[i - 1] < array[i] && array[i + 1] < array[i];
    if (!isPeak) {
      i++;
      continue;
    }
    let leftIdx = i - 2;
    while (leftIdx >= 0 && array[leftIdx] < array[leftIdx + 1]) {
      leftIdx--;
    }
    let rightIdx = i + 2;
    while (rightIdx < array.length && array[rightIdx] < array[rightIdx - 1]) {
      rightIdx++;
    }
    const currentPeakLength = rightIdx - leftIdx - 1;
    longestPeakLength = Math.max(longestPeakLength, currentPeakLength);
    i = rightIdx;
  }
  return longestPeakLength;
}

### Optimal Space & Time Complexity

:::spoiler Answer
O(n) time | O(1) space - where n is the length of the input array
:::
---

### Everyone's
#### Find the peak

:::spoiler 東

// Time O(n) | Space O(n) - where n is the length of input array
function longestPeak(array) {
  let peakIdx = [];
  for(let i = 1; i < array.length - 1; i++){
    if(array[i-1] < array[i] && array[i] > array[i+1]) peakIdx.push(i);
  }

  if(peakIdx.length === 0) return 0;

  const peakLength = peakIdx.map((idx) => getPeakLength(idx, array));
  return Math.max(...peakLength);
}

function getPeakLength(peakIdx, array){
  let startIdx, endIdx;
  for(let i = peakIdx; i > 0; i--){
    if(array[i] > array[i-1]){
      startIdx = i - 1;
    } else break;
  }
  for(let i = peakIdx; i < array.length - 1; i++){
    if(array[i] > array[i + 1]){
      endIdx = i + 1;
    } else break;
  }
  return endIdx - startIdx + 1;
}

- Set a default value for `startIdx` and `endIdx`

:::

<br>

:::spoiler YC

function longestPeak(array) {
  if(array.length < 3) return 0;
  let maxLen = 0;
  for(let i = 1; i < array.length - 1; i++){
    const curr = i;
    let left = i - 1;
    let right = i + 1;

    const isPeak = array[left] < array[curr] && array[curr] > array[right];
    
    if(!isPeak) continue;

    let len = 3;
        
    //left /
    while(left > 0){
      if(array[left] <= array[left-1]){
        break;
      }
      len++;
      left--;
    }
    
    //right \
    while(right < array.length - 1){
      if(array[right] <= array[right + 1]){
        break;
      }
      len++;
      right++;
    }
    maxLen = Math.max(maxLen, len);
    i = right;
  }
  return maxLen;
}

:::

<br>

:::spoiler Hao (solution 2)

/*
 * Time complexity: O(n) which n stands for array.length
 * Space complexity: O(1)
 */

function longestPeak(array) {
  let maxConut = 0;

  for (let i = 1; i < array.length; i += 1) {
    if (!(array[i - 1] < array[i] && array[i + 1] < array[i])) continue;

    let peakCount = 1;

    let j = i;
    while (j > 0 && array[j - 1] < array[j]) {
      peakCount += 1;
      j -= 1;
    }

    let k = i;
    while (k < array.length - 1 && array[k + 1] < array[k]) {
      peakCount += 1;
      k += 1;
    }

    if (peakCount > maxConut) maxConut = peakCount;
  }

  return maxConut;
}

:::

#### Find the current state

:::spoiler 月

/*
    Time: O(n), Space: O(1)
    n is the length of array.
*/
function longestPeak(arr) {
  let up = down = result = 0;
  for (let i = 1; i < arr.length; i++) {
      const height = arr[i];
      if (height === arr[i - 1] || down && height > arr[i - 1])
          up = down = 0;
      if (height > arr[i - 1]) up += 1;
      if (height < arr[i - 1]) down += 1;
      if (up && down) result = Math.max(result, up + down + 1);
  }
  return result;
}

- I like this solution.
:::

<br>

:::spoiler Hao (solution 1)

/*
 * Time complexity: O(n) which n stands for array.length
 * Space complexity: O(1)
 */

const peak = {
  'ASC': 'ASC',
  'DESC': 'DESC',
  'NOT': 'NOT',
};

function longestPeak(array) {
  let maxPeak = 0;
  let isPeakEnd = false;
  let count = 0;
  let curState = peak.NOT;

  for (let i = 1; i < array.length; i += 1) {
    switch (curState) {
      case peak.NOT: {
        if (array[i - 1] < array[i]) curState = peak.ASC;
        else curState = peak.NOT;
        break;
      }

      case peak.ASC: {
        if (array[i - 1] < array[i]) curState = peak.ASC;
        else if (array[i - 1] > array[i]) curState = peak.DESC;
        else curState = peak.NOT;
        break;
      };

      case peak.DESC: {
        if (array[i - 1] > array[i]) break;

        isPeakEnd = true;

        if (array[i - 1] < array[i]) curState = peak.ASC;
        else curState = peak.NOT;
        break;
      }
    }

    if (i === array.length - 1 && curState === peak.DESC) {
      count += 1;
      isPeakEnd = true;
    };

    if (isPeakEnd) {
      if (count > maxPeak) maxPeak = count;
      count = 0;
      isPeakEnd = false;
    };

    switch (curState) {
      case peak.NOT: {
        count = 0;
        break;
      }

      case peak.ASC: {
        if (!count) count = 2;
        else count += 1;
        break;
      }

      case peak.DESC: {
        count += 1;
        break;
      }
    }
  }

  return maxPeak;
}

:::

<br>

---

## Supplement / Discussion