Longest Bitonic Subarray

Time: O(n)

Space: O(1)

Problem Overview

A bitonic subarray rises (non-decreasing) then falls (non-increasing), possibly with only one of the two phases.

Intuition

A bitonic subarray rises (non-decreasing) then falls (non-increasing), possibly with only one of the two phases. Scan once: grow an ascent, then a descent, record the window length, and advance the start to the last peak so overlapping bitonic shapes share that peak instead of restarting from scratch.

Algorithm

1If n ≤ 1, return n.
2Maintain start of the current window, j as the right edge, and nextStart for the following window.
3While j < n−1: advance j while arr[j] ≤ arr[j+1] (ascent).
4Then advance j while arr[j] ≥ arr[j+1] (descent); on each strict drop arr[j] > arr[j+1], set nextStart = j+1.
5Update maxLen with j − start + 1; set start = nextStart and continue.
6Return maxLen.

Example Walkthrough

Input: arr = [12, 4, 78, 90, 45, 23]

1. From 12 down to 4 (descent-only), then climb 4→78→90 and fall 90→45→23.
2. Window [4, 78, 90, 45, 23] has length 5.
3. nextStart lands after the peak so a later window can reuse index of 90 if needed.
4. Answer is 5 (the longest bitonic contiguous segment).

Output: 5

Common Pitfalls

• This is a contiguous subarray, not a subsequence — do not skip elements.
• Equals are allowed on both the rising and falling sides (≤ and ≥), so plateaus still count.
• Remember nextStart on strict decreases so adjacent bitonic parts that share a peak are not missed.
• Purely increasing or purely decreasing arrays are valid bitonic of length n.

Longest Bitonic Subarray.java

Java

// Approach: One pass over contiguous windows. Extend a non-decreasing ascent, then a
// non-increasing descent; track max window length. On a strict drop, remember nextStart
// so the next bitonic window can begin at that peak (shared between adjacent shapes).
// Time: O(n) Space: O(1)

class Solution {

    public int bitonic(int[] arr) {
        int n = arr.length;

        if (n <= 1) {
            return n;
        }

        int maxLen = 1;
        int start = 0;
        int nextStart = 0;
        int j = 0;

        while (j < n - 1) {
            // 1. Look for the end of the ascent (increasing sequence)
            while (j < n - 1 && arr[j] <= arr[j + 1]) {
                j++;
            }

            // 2. Look for the end of the descent (decreasing sequence)
            while (j < n - 1 && arr[j] >= arr[j + 1]) {
                // Safely mark where the next potential sequence should start
                if (j < n - 1 && arr[j] > arr[j + 1]) {
                    nextStart = j + 1;
                }
                j++;
            }

            // 3. Update the maximum length found so far
            maxLen = Math.max(maxLen, j - start + 1);
            // 4. Reset start position for the next transition window
            start = nextStart;
        }

        return maxLen;
    }
}

Was this solution helpful?