.png)
Maximum Length Bitonic Subarray
Problem Statement
You are given an integer array arr.
Find the maximum length of a contiguous subarray that is bitonic.
A bitonic subarray:
- First strictly increases
- Then strictly decreases
- Either increasing or decreasing part must be non-empty
Example 1
Input
arr = [12, 4, 78, 90, 45, 23]
Output
5
Example 2
Input
arr = [10, 20, 30, 40]
Output
4
Example 3
Input
arr = [10, 10, 10]
Output
1
Why This Problem Is Important
- Classic array pattern interview question
- Tests increasing + decreasing logic
- Foundation for mountain array problems
- Asked in Amazon, Microsoft, Flipkart
- Appears in DP & two-pointer discussions
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix Inc + Prefix Dec (DP) | O(n) | O(n) |
| Approach 3 | Single Pass (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
Check every possible subarray and verify whether it is bitonic.
Time & Space
- Time: O(n²)
- Space: O(1)
C Implementation
#include
int isBitonic(int arr[], int l, int r) {
int i = l;
// increasing part
while (i < r && arr[i] < arr[i+1]) i++;
if (i == l || i == r) return 0;
// decreasing part
while (i < r && arr[i] > arr[i+1]) i++;
return i == r;
}
int main() {
int arr[] = {12,4,78,90,45,23};
int n = 6, ans = 1;
for(int i=0;i ans) ans = j-i+1;
}
}
}
printf("%d", ans);
return 0;
}
Output:
5
C++ Implementation
#include
using namespace std;
bool isBitonic(vector& a, int l, int r) {
int i = l;
while(i < r && a[i] < a[i+1]) i++;
if(i == l || i == r) return false;
while(i < r && a[i] > a[i+1]) i++;
return i == r;
}
int main() {
vector arr = {12,4,78,90,45,23};
int n = arr.size(), ans = 1;
for(int i=0;iOutput:
5
Java Implementation
class Bitonic {
static boolean isBitonic(int[] a, int l, int r) {
int i = l;
while(i < r && a[i] < a[i+1]) i++;
if(i == l || i == r) return false;
while(i < r && a[i] > a[i+1]) i++;
return i == r;
}
public static void main(String[] args) {
int[] arr = {12,4,78,90,45,23};
int n = arr.length, ans = 1;
for(int i=0;iOutput:
5
Python Implementation
def is_bitonic(a, l, r):
i = l
while i < r and a[i] < a[i+1]:
i += 1
if i == l or i == r:
return False
while i < r and a[i] > a[i+1]:
i += 1
return i == r
arr = [12,4,78,90,45,23]
n = len(arr)
ans = 1
for i in range(n):
for j in range(i+2, n):
if is_bitonic(arr, i, j):
ans = max(ans, j-i+1)
print(ans)
Output:
5
JavaScript Implementation
function isBitonic(a, l, r) {
let i = l;
while (i < r && a[i] < a[i+1]) i++;
if (i === l || i === r) return false;
while (i < r && a[i] > a[i+1]) i++;
return i === r;
}
let arr = [12,4,78,90,45,23];
let n = arr.length;
let ans = 1;
for (let i = 0; i < n; i++) {
for (let j = i + 2; j < n; j++) {
if (isBitonic(arr, i, j)) {
ans = Math.max(ans, j - i + 1);
}
}
}
console.log(ans);
Output:
5
C# Implementation
using System;
class Program {
static bool IsBitonic(int[] a, int l, int r){
int i = l;
while(i < r && a[i] < a[i+1]) i++;
if(i == l || i == r) return false;
while(i < r && a[i] > a[i+1]) i++;
return i == r;
}
static void Main(){
int[] arr = {12,4,78,90,45,23};
int n = arr.Length, ans = 1;
for(int i=0;iOutput:
5
Approach 2: Prefix Increasing + Prefix Decreasing (DP)
Idea
Compute:
- inc[i] → increasing subarray ending at i
- dec[i] → decreasing subarray starting at i
Time & Space
- Time: O(n)
- Space: O(n)
C++ Implementation
#include
using namespace std;
int main(){
int arr[]={12,4,78,90,45,23};
int n=6;
vector inc(n,1), dec(n,1);
// increasing lengths
for(int i=1;iarr[i-1]) inc[i]=inc[i-1]+1;
// decreasing lengths
for(int i=n-2;i>=0;i--)
if(arr[i]>arr[i+1]) dec[i]=dec[i+1]+1;
int ans=1;
for(int i=0;iOutput:
5
Java Implementation
import java.util.*;
class Bitonic {
public static void main(String[] args){
int[] arr={12,4,78,90,45,23};
int n=arr.length;
int[] inc=new int[n];
int[] dec=new int[n];
Arrays.fill(inc,1);
Arrays.fill(dec,1);
for(int i=1;iarr[i-1]) inc[i]=inc[i-1]+1;
for(int i=n-2;i>=0;i--)
if(arr[i]>arr[i+1]) dec[i]=dec[i+1]+1;
int ans=1;
for(int i=0;iOutput:
5
Python Implementation
arr=[12,4,78,90,45,23]
n=len(arr)
inc=[1]*n
dec=[1]*n
for i in range(1,n):
if arr[i]>arr[i-1]:
inc[i]=inc[i-1]+1
for i in range(n-2,-1,-1):
if arr[i]>arr[i+1]:
dec[i]=dec[i+1]+1
ans = max(inc[i]+dec[i]-1 for i in range(n))
print(ans)
Output:
5
JavaScript Implementation
let arr=[12,4,78,90,45,23];
let n=arr.length;
let inc=new Array(n).fill(1);
let dec=new Array(n).fill(1);
for(let i=1;iarr[i-1]) inc[i]=inc[i-1]+1;
for(let i=n-2;i>=0;i--)
if(arr[i]>arr[i+1]) dec[i]=dec[i+1]+1;
let ans=1;
for(let i=0;iOutput:
5
C# Implementation
using System;
class Program {
static void Main(){
int[] arr={12,4,78,90,45,23};
int n=arr.Length;
int[] inc=new int[n];
int[] dec=new int[n];
for(int i=0;iarr[i-1]) inc[i]=inc[i-1]+1;
for(int i=n-2;i>=0;i--)
if(arr[i]>arr[i+1]) dec[i]=dec[i+1]+1;
int ans=1;
for(int i=0;iOutput:
5
Approach 3: Single Pass (Optimal)
Idea
Track increasing and decreasing lengths in one traversal.
Time & Space
- Time: O(n)
- Space: O(1)
C++ Implementation
#include
using namespace std;
int main(){
int arr[]={12,4,78,90,45,23};
int n=6, inc=1, dec=0, ans=1;
for(int i=1;i arr[i-1]){
inc++;
dec=0;
}
else if(arr[i] < arr[i-1]){
if(inc > 1) dec++;
ans = max(ans, inc + dec);
}
else{
inc=1;
dec=0;
}
}
cout<Output:
5
Python Implementation
arr=[12,4,78,90,45,23]
inc=1
dec=0
ans=1
for i in range(1,len(arr)):
if arr[i] > arr[i-1]:
inc+=1
dec=0
elif arr[i] < arr[i-1]:
if inc > 1:
dec+=1
ans=max(ans,inc+dec)
else:
inc=1
dec=0
print(ans)
Output:
5
Java Implementation
class BitonicOnePass {
public static void main(String[] args){
int[] arr={12,4,78,90,45,23};
int n=arr.length, inc=1, dec=0, ans=1;
for(int i=1;i arr[i-1]){
inc++;
dec=0;
}
else if(arr[i] < arr[i-1]){
if(inc > 1) dec++;
ans=Math.max(ans, inc+dec);
}
else{
inc=1;
dec=0;
}
}
System.out.println(ans);
}
}
Output:
5
JavaScript Implementation
let arr=[12,4,78,90,45,23];
let inc=1, dec=0, ans=1;
for(let i=1;i arr[i-1]){
inc++;
dec=0;
}
else if(arr[i] < arr[i-1]){
if(inc > 1) dec++;
ans=Math.max(ans, inc+dec);
}
else{
inc=1;
dec=0;
}
}
console.log(ans);
Output:
5
C# Implementation
using System;
class Program {
static void Main(){
int[] arr={12,4,78,90,45,23};
int inc=1, dec=0, ans=1;
for(int i=1;i arr[i-1]){
inc++;
dec=0;
}
else if(arr[i] < arr[i-1]){
if(inc > 1) dec++;
ans=Math.Max(ans, inc+dec);
}
else{
inc=1;
dec=0;
}
}
Console.WriteLine(ans);
}
}
Output:
5
Summary
- Brute Force: Concept clarity
- DP Approach: Clean & reliable
- Single Pass: Best for interviews
- Applies directly to Longest Mountain / Bitonic problems
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
