How to solve this problem?

#1

We are given an array of integers and a range, we need to find whether the subarray which falls in this range has values in the form of a mountain or not. All values of the subarray are said to be in the form of a mountain if either all values are increasing or decreasing or first increasing and then decreasing. More formally a subarray [a1, a2, a3 … aN] is said to be in form of a mountain if there exists an integer K, 1 <= K <= N such that,
a1 <= a2 <= a3 … <= aK >= a(K+1) >= a(K+2) …. >= aN
You have to process Q queries. In each query you are given two integer L and R, denoting starting and last index of the subarrays respectively.

The time constraint is O(n +q)

#2

@nidhigupta847

  • Approach: The problem has multiple queries so for each query the solution should be calculated with least possible time complexity. So create two extra spaces of the length of the original array. For every element find the last index on the left side which is increasing i.e. greater than its previous element and find the element on the right side will store the first index on the right side which is decreasing i.e. greater than its next element. If these value can be calculated for every index in constant time then for every given range the answer can be given in constant time.
  • Algorithm:
    1. Create two extra spaces of length n , left and right and a extra variable lastptr
    2. Initilize left[0] = 0 and lastptr = 0
    3. Traverse the original array from second index to the end
    4. For every index check if it is greater than the pervious element, if yes then update the lastptr with the current index.
    5. For every index store the lastptr in left[i]
    6. initilize right [N-1] = N-1 and lastptr = N-1
    7. Traverse the original array from second last index to the start
    8. For every index check if it is greater than the next element, if yes then update the lastptr with the current index.
    9. For every index store the lastptr in right[i]
    10. Now process the queries
    11. for every query l, r , if right[l] >= left[r] then print yes else no
#3

Yeah I saw this on gfg but could you elaborate how is this right[l] >= left[r] giving us the answer ?

#4

@nidhigupta847
Arr[] = [2 3 2 4 4 6 3 2]
Using above procedure building left and right array,
left[] = [0 1 1 3 3 5 5 5]
right[] = [1 1 5 5 5 5 6 7]
Range = [2, 4]
Now right[2] is 5 and left[4] is 3 that means at
index 2 first decreasing element is right to the
last increasing element at index 4, so they should
have a mountain form.

Range = [0, 3]
Now right[0] is 1 and left[3] is 3 that means at
index 0 first decreasing element is left to the
last increasing element at index 3, so the subarray
corresponding to this range does not have mountain
form. We can see this in the array itself, right[0]
is 1 which is value 3 and left[3] is 3 which is
value 4 so 4 which is in increasing form (due to
previous value 2) comes later to 3 which is in
decreasing form (due to next value 2), mountain form
was not possible here, same information is carried
out with the help of left and right array.

#5

Okay but for query 5 7 the subarray is [6,3,2] this logic says this subarray forms a mountain but how ?

#6

@nidhigupta847
The output is yes , subarray is [6 3 2],
so subarray first increases and then decreases .

#7

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.

#8 
bool isIncreasing(int*a, int start, int end){
  if(start >= end){
      return true;
  }
  
  if(a[start] < a[start+1]){
      return isIncreasing(a, start+1, end);
  }
  return false;

}

bool isDecreasing(int*a, int start, int end){
if(start >= end)
return true;

  if(a[start] > a[start+1])
  return isDecreasing(a, start+1, end);
  
  return false;

}

bool isMountain(int*a, int n, int start, int end){
int flag = 0;
for(int i = start; i < end; i++){
if(a[i] > a[i+1] && i == start){
return false;
}
else if(a[i] < a[i+1]){
if(flag == 0)
continue;
else
return false;
}
else if(a[i] > a[i+1]){
flag = 1;
}
}

  return true;

}
vector processQueries(int a[], int n, vector<pair<int, int>> &queries,
int q) {
// code here

    vector<bool> ans;
   
    for(int i = 0; i < q; i++){
        // cout << "index" << i << endl;
         bool ans1 = false, ans2 = false, ans3 = false;
        ans1 = isIncreasing(a, queries.at(i).first, queries.at(i).second);
        // cout << "ans1" << ans1;
        if(ans1 == false)
         ans2 = isDecreasing(a, queries.at(i).first, queries.at(i).second);
        //  cout << "ans2" << ans2;
        if(ans1 == false && ans2 == false)
        ans3 = isMountain(a, n, queries.at(i).first, queries.at(i).second);
        // cout << "ans3" << ans3;
        
        if(ans1 == false && ans2 == false && ans3 == false){
           ans.push_back(false);
            continue;
        }
        ans.push_back(true);
    }

   return ans; 
}

I have written this solution of this problem but it’s not passing one test case.Can anyone please explain where is the problem?
In this code I have made 3 functions one will check whether it’s a increasing mountain other will check if it’s a decreasing mountain and last function will check if it’s a first increasing and then decreasing type mountain