Longest Turbulent subarrays solution
We have given an Integer array we have to find the size of the longest Turbulent subarrays. Before going to solve this problem we have to understand what is Turbulent subarray?
A subarray is said to be Turbulent if the comparison sign between each adjacent pair of items in a subarray flips, the subarray is turbulent.
Let us see some examples for better understanding Turbulent subarrays.
Input: arr = [2,7,34,8,9,21,45,12]
Output: 4
Example 2:
Input: arr = [10,3,12,30,28,3]
Output: 3
Example 3:
Input: arr = [20]
Output: 1
Solution of a Longest turbulent subarray in Java
class Solution {
public int maxTurbulenceSize(int[] arr) {
if(arr.length==1) return 1;
if(arr.length==2 && arr[0]!=arr[1]) return 2;
boolean b=true;
for(int i=0;i<arr.length;i++)
{
if(arr[0]!=arr[i]) b=false;
if(!b) break;
}
if(b) return 1;
int count=2;
int max=0;
for(int i=1;i<arr.length-1;i++)
{
if((arr[i]>arr[i-1] && arr[i]>arr[i+1]) || (arr[i]<arr[i-1] && arr[i]<arr[i+1]))
{
count=count+1;
}
else
{
count=2;
}
if(arr[i-1]!=arr[i]) max=Math.max(max,count);
}
return max;
}
}
> Also Read - Largest Rectangle in Histogram
Solution of a Longest turbulent subarray in C++
class Solution {
int maxTurbulenceSize(vector<int>& arr) {
int max = 0, c = 1;
if (arr.size() == 1) return 1;
bool b;
for (int i = 0; i < arr.size() - 1; ++i) {
if (arr[i] == arr[i + 1]) {
max = c > max ? c : max;
c = 1;
}
else if((c == 1) || ((arr[i] > arr[i + 1] ? true : false) ^ b)) {
c++;
b = arr[i] > arr[i + 1] ? 1 : 0;
}
else {
max = c > max ? c : max;
c = 1;
--i;
}
}
max = c > max ? c : max;
return max;
}
};
The above codes are most efficient and with very little time C complexity you can your own approach to getting a more efficient and optimized solution.
