Maximum length Bitonic

#1


I am getting time limit exceed error in this code. What is a better approach to this problem?

#2

This question expects linear time complexity (O(n)) as per the constraints given.
Create two auxiliary arrays - arr1 and arr2 of the same size as our original array.
v is our original array.
arr1 is constructed from left to right such that arr1[i] contains the length of the nondecreaing subarray ending at v[i].
arr2 is constructed from right to left such that arr2[i] contains length of nonincreasing subarray starting at v[i].
Maximum value of (arr1[i] + arr2[i] - 1) will be our answer.

#3

My solution is also of the order O(n). Please find the error in my code.

#4

Your solution is of the order O(n^2).
while(i<n)
{
while(input[i]>=input[i-1] && i < n )
{
i++;
}
while(input[i]<=input[i-1] && i < n )
{
i++;
}
max_length = max(max_length, i-start);
start = i-1;
}
The outer while loop runs for O(n) time and the inner while loops can run for O(n) time as well in the worst case. So the overall worst case time complexity of your code is O(n^2).

#5

Since the value of i is same for inner loop and outer loop and is only increasing so the solution is O(n) only. Each element is visted once, either in upper while loop or in second while loop.

#6

Actually your code is giving wrong answer when it is running on the hidden test cases.
And yes you are right. Your code’s complexity is O(n) only.
But there’s some problem with the logic of the code.

#7

@Kajal Please mark your doubt as resolved if you are satisfied

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.