Longest Peak

Tags

Longest Peak

Category

Arrays

Difficulty

Medium

Problem Statement

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

Intuition

A peak has a clear structure: a strictly increasing run followed by a strictly decreasing run, with the tip being the transition point. By scanning for tips — elements strictly greater than both their neighbors — and expanding outward from each tip, we can measure each peak's length and track the maximum.

Approach

  1. Initialize longestPeak = 0.
  2. Start at index i = 1 and iterate up to length - 2 (only interior elements can be tips).
  3. Check if array[i] is a tip: array[i - 1] < array[i] > array[i + 1].
  4. If it is a tip, expand left while the sequence is strictly increasing and expand right while it is strictly decreasing.
  5. Compute the peak length as right - left + 1 and update longestPeak if larger.
  6. Set i = right to skip over the already-processed peak, then continue.
  7. Return longestPeak.

Pseudocode

function longestPeak(array):
    longestPeak = 0
    i = 1

    while i < length(array) - 1:
        isPeak = array[i - 1] < array[i] and array[i] > array[i + 1]
        if not isPeak:
            i += 1
            continue

        left = i - 2
        while left >= 0 and array[left] < array[left + 1]:
            left -= 1
        left += 1

        right = i + 2
        while right < length(array) and array[right] < array[right - 1]:
            right += 1
        right -= 1

        currentPeak = right - left + 1
        longestPeak = max(longestPeak, currentPeak)
        i = right

    return longestPeak

Time & Space Complexity

  • Time: O(n) — although there is an inner expansion loop, each element is visited at most twice (once by the outer loop, once during expansion), so total work is linear.
  • Space: O(1) — only a few integer variables are used.

Key Insights

  • Skipping i forward to right after processing a peak avoids re-examining elements and keeps the algorithm linear.
  • A peak requires at least 3 elements: one ascending, the tip, and one descending.
  • Plateaus (equal adjacent elements) break a peak; the definition requires strict increase and strict decrease.

Edge Cases

  • Array with fewer than 3 elements: no peak is possible, return 0.
  • Array with no peaks (e.g., sorted ascending or descending): return 0.
  • Multiple peaks of the same length: return that shared length.
  • Entire array forms one peak: return the full length.
  • Plateaus at the top or sides prevent peak formation at those positions.

Linked mentions