Problem Statement
Given an array arr[] of positive integers, find the maximum length of a bitonic subarray.
A bitonic subarray is a contiguous part of the array that:
Formally, there exists an index k such that:
arr[i] <= arr[i+1] <= ... <= arr[k]
arr[k] >= arr[k+1] >= ... >= arr[j]
Example
Input
arr = [12, 4, 78, 90, 45, 23]
Output
5
Explanation
The longest bitonic subarray is:
[4, 78, 90, 45, 23]
It first increases:
4 → 78 → 90
Then decreases:
90 → 45 → 23
Length = 5
Approach
Instead of checking every possible subarray, we calculate two helper arrays.
Step 1: Create an Increasing Array (inc[])
inc[i] stores the length of the longest non-decreasing subarray ending at index i.
Example
arr = [12, 4, 78, 90, 45, 23]
inc = [1, 1, 2, 3, 1, 1]
Explanation
| Index | Value | inc[i] | Reason |
|---|
| 0 | 12 | 1 | Starts here |
| 1 | 4 | 1 | 4 < 12 |
| 2 | 78 | 2 | 4 ≤ 78 |
| 3 | 90 | 3 | 78 ≤ 90 |
| 4 | 45 | 1 | 45 < 90 |
| 5 | 23 | 1 | 23 < 45 |
Step 2: Create a Decreasing Array (dec[])
dec[i] stores the length of the longest non-increasing subarray starting from index i.
Example
dec = [2, 1, 1, 3, 2, 1]
Explanation
| Index | Value | dec[i] | Reason |
|---|
| 5 | 23 | 1 | Last element |
| 4 | 45 | 2 | 45 ≥ 23 |
| 3 | 90 | 3 | 90 ≥ 45 |
| 2 | 78 | 1 | 78 < 90 |
| 1 | 4 | 1 | 4 < 78 |
| 0 | 12 | 2 | 12 ≥ 4 |
Step 3: Calculate Bitonic Length
For every index:
Bitonic Length = inc[i] + dec[i] - 1
Why Subtract 1?
The peak element is counted in both arrays, so we subtract 1 to avoid counting it twice.
Example
inc = [1, 1, 2, 3, 1, 1]
dec = [2, 1, 1, 3, 2, 1]
| Index | inc | dec | Bitonic Length |
|---|
| 0 | 1 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 3 | 3 | 3 | 5 |
| 4 | 1 | 2 | 2 |
| 5 | 1 | 1 | 1 |
Maximum = 5
Java Solution
class Solution {
public int bitonic(int[] arr) {
int n = arr.length;
// Arrays to store increasing and decreasing lengths
int[] inc = new int[n];
int[] dec = new int[n];
// First element always has length 1
inc[0] = 1;
// Build increasing array
for (int i = 1; i < n; i++) {
if (arr[i] >= arr[i - 1])
inc[i] = inc[i - 1] + 1;
else
inc[i] = 1;
}
// Last element always has length 1
dec[n - 1] = 1;
// Build decreasing array
for (int i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[i + 1])
dec[i] = dec[i + 1] + 1;
else
dec[i] = 1;
}
int ans = 1;
// Find maximum bitonic length
for (int i = 0; i < n; i++) {
ans = Math.max(ans, inc[i] + dec[i] - 1);
}
return ans;
}
}
Code Explanation
Step 1
int n = arr.length;
Stores the size of the array.
Step 2
int[] inc = new int[n];
int[] dec = new int[n];
Creates two helper arrays:
Step 3
inc[0] = 1;
The first element always forms a non-decreasing sequence of length 1.
Step 4
for (int i = 1; i < n; i++) {
if (arr[i] >= arr[i - 1])
inc[i] = inc[i - 1] + 1;
else
inc[i] = 1;
}
Builds the increasing array.
Example
arr = [2, 4, 4, 7]
Execution:
inc[0] = 1
4 >= 2
inc[1] = 2
4 >= 4
inc[2] = 3
7 >= 4
inc[3] = 4
Final result:
inc = [1, 2, 3, 4]
Step 5
dec[n - 1] = 1;
The last element always forms a decreasing sequence of length 1.
Step 6
for (int i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[i + 1])
dec[i] = dec[i + 1] + 1;
else
dec[i] = 1;
}
Builds the decreasing array.
Example
arr = [9, 7, 5, 5]
Execution:
dec[3] = 1
5 >= 5
dec[2] = 2
7 >= 5
dec[1] = 3
9 >= 7
dec[0] = 4
Result:
dec = [4, 3, 2, 1]
Step 7
int ans = 1;
Stores the maximum bitonic length found so far.
Step 8
for (int i = 0; i < n; i++) {
ans = Math.max(ans, inc[i] + dec[i] - 1);
}
Calculates the bitonic length for every index.
Example
inc = [1, 1, 2, 3, 1, 1]
dec = [2, 1, 1, 3, 2, 1]
At index 3:
3 + 3 - 1 = 5
The -1 removes the duplicate count of the peak element.
Step 9
return ans;
Returns the maximum bitonic subarray length.
Dry Run
Input
arr = [12, 4, 78, 90, 45, 23]
After Building inc[]
[1, 1, 2, 3, 1, 1]
After Building dec[]
[2, 1, 1, 3, 2, 1]
Calculation
| Index | inc | dec | Length |
|---|
| 0 | 1 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 3 | 3 | 3 | 5 |
| 4 | 1 | 2 | 2 |
| 5 | 1 | 1 | 1 |
Maximum = 5
Complexity Analysis
| Complexity | Value |
|---|
| Time Complexity | O(n) |
| Space Complexity | O(n) |
Why O(n)?
We traverse the array three times:
Build inc[]
Build dec[]
Find the maximum bitonic length
Each traversal takes O(n) time.
Why O(n) Space?
Two additional arrays of size n are used:
Therefore, auxiliary space is O(n).
Key Takeaways
A bitonic subarray first increases (or remains equal) and then decreases (or remains equal).
inc[] stores the length of the longest non-decreasing subarray ending at each index.
dec[] stores the length of the longest non-increasing subarray starting at each index.
The bitonic length at index i is calculated as:
inc[i] + dec[i] - 1
The subtraction of 1 prevents counting the peak element twice.
The solution runs in O(n) time and O(n) space, making it efficient for large arrays.
Summary
The longest bitonic subarray problem can be solved efficiently using two helper arrays that track increasing and decreasing sequence lengths. By computing inc[] and dec[], we can determine the bitonic length centered at every index and find the maximum value in linear time. This approach avoids checking all possible subarrays and provides an optimal O(n) solution suitable for large datasets.
Join the conversation! Your thoughts help the community grow.